Binary Search   이진 검색

1. 이진 검색 (Binary Search)                              

  ㅇ 실행 방식
     - 기 정렬되어있는 순서 리스트에서 만 가능한 검색 방법
     - 중앙 위치로부터 탐색 범위를 반씩 줄이면서 자료를 찾는 방법              ☞ 분할 정복법 참조

  ㅇ 시간복잡도 : O(log n)                                   ☞ 시간복잡도 표기 예 (로그시간) 참조
     - 매번 그 크기를 반씩 줄여나감 
        . 1번째 (n개), 2번째 (n/2개), 3번째 (n/2 * 1/2), ... , k번째 (n * (1/2)k)
        . 마지막 남는 개수를 1로 하면, n*(1/2)k = 1, 2k = n, k = log2 n 

  ㅇ 적용 : 정렬된 자료 만 가능


2. 이진 검색의 알고리즘 표현 (반복적 구현)

  ㅇ 알고리즘의 표현 (by 자바스크립트)
      
function binarySearchIterative(array, n){
    let low = 0;
    let high = array.length-1;

    while (low <= high) {
        let mid = Math.floor( (high + low) / 2 );
        // (오버플로우 방지) => mid = low + Math.floor((high - low)/2)
        
        if (n > array[mid]) {
            low = mid + 1;
        } else if (n < array[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
     - 입력 : array 배열, n 검색할 값
     - 출력 : 검색된 위치 인덱스 또는 -1(검색실패)

  ㅇ 알고리즘의 단계
     - ① 최초 하한은 배열의 첫째값(0), 상한은 배열의 끝값(길이-1)
     - ② 상한,하한 사이에 중간값을 찾는 루프
         . ⓐ 중간값 지정 (상한,하한의 가운데)
         . ⓑ 찾던 값이 중간값 보다 큰지 작은지에 따라, 
              하한 또는 상한을 하나씩 늘리거나 줄이면서 재지정
         . ⓒ 찾던 값이 중간값 이면, 해당 인덱스를 반환하고, 검색 끝냄
     - ③ 상한,하한 구간을 반씩 줄여가는 중에 역전되면,
          이 배열에 찾는 값이 없는 것이고, -1을 반환


3. 이진 검색의 알고리즘 표현 (재귀적 구현)

  ㅇ ... (작성중) ...