Binary Search [이분탐색]

 

이분탐색은 오름차순 정렬된 배열에서 특정 값을 찾아 인덱스를 반환하는 search algorithm입니다.

코드는 다음과 같습니다.

int binarySearch(int A[], int x, int low, int high){
    int mid;
    if(low>high) return -1;
    else{
        mid = (low+high)/2;
        if(A[mid]==x) return mid;
        else if(A[mid]>x) return binarySearch(A,x,low,mid-1);
        else return binarySearch(A,x,mid+1,high);
    }
}

low와 high의 초기값은 각각 탐색하고자 하는 배열의 처음 인덱스와 마지막 인덱스입니다.

즉 mid는 현재 탐색하고 있는 배열의 가운데 인덱스를 가리키게 됩니다.

 

만약 A[mid]가 찾고자 하는 값이라면, mid를 반환하고 코드가 종료됩니다.

 

여기서 배열 A는 오름차순이므로, A[mid] 위치가 찾고자 하는 값이 아니라면 mid보다 작은 인덱스는 A[mid] 이하이고, 큰 인덱스는 A[mid] 이상인 것이 보장되므로, A[mid]>x 라면 low와 mid-1 사이, 그렇지 않다면 mid+1과 high 사이를 탐색합니다.

 

만약 배열에 값이 존재하지 않는 경우, low는 high보다 1 커질 것이므로 low>high일 때 코드를 종료합니다.

 

 다음은 worth-time-complexity (최악의 경우의 시간 복잡도)를 구하는 과정입니다.

최악의 경우 시간복잡도

따라서 binary search의 worth time complexity는 𝜃(lg(n)) 입니다.