Binary Search

이분검색 ( Binary Search )

• Time : O ( logN )
• Space : O ( n )

 

탐색을 요구하는 대상은 정렬이 필요하다 ( "오름차순" 이 아니여도 상관없다. 방향에 따른 pivot 위치만 바꾸면 된다 )

( 정렬은 다른 포스팅에서 다루기로 한다 )

 

정렬된 대상의 중간 값으로 찾는 값의 크고 작음을 이분하여 다음 순서에 탐색하는 공간을 반씩 줄여간다.

전체 공간을 반씩 줄여가기 때문에 탐색 공간이 log(2) 로 줄어든다.

탐색 공간이 더 이상 없으면 ( low > high ) 탐색에 실패한다.

function search(arr, x) {
	
    const length = arr.length;
    let low = 0;
    let high = length;
    let mid;
    let idx = 0; // result
    
    while (low < hight && idx == 0) {
    	mid = Math.floor( (low + high) / 2 ); // Round Down
        if (x == arr[mid]) {
        	idx = mid;
            // success
            return idx;
        } else if (x < arr[mid]) {
        	high = mid - 1; // move right    
        } else {
        	low = mid + 1; // move left
        }
    }
    
    // fail
    return -1;
}