[알고개념] 10. 이분탐색

1. 이분탐색

이분탐색은 우리가 익히 잘 알고 있는 up down 숫자 맞추기 게임과 매우 유사하다. 예를 들어 3을 생각하고 1~100까지의 수 중에서 하나를 생각해서 맞춰보라고 하면 50 -> 25 -> 12 -> 6 -> 3 과 같은 식으로 2씩 나눠서 답을 구할 것이다. 이 과정이 바로 이분탐색이다. 이분 탐색을 하기 위한 전제 조건은 "데이터들이 정렬"되어 있어야 한다.

이분 탐색 코드는 아래와 같이 짤 수 있다. 재귀 호출을 이용해도 되고 while (l <= r)과 같은 방식으로 탐색해도 된다.

int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
 
        // If the element is present at the middle
        if (arr[mid] == x)
            return mid;
 
        // If element is smaller than mid, then it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
 
        // Else right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
 
    return -1;
}