이진 탐색 알고리즘 (binary search algorithm)

주어진 배열에서 특정한 요소 target 을 찾아내는 상황을 가정해 봅시다. 가장 쉽게 떠 올릴 수 있는 방법은 배열의 요소 하나하나와 target 값이 같은지를 순차적으로 모두 비교하는 것입니다. 만약 배열의 크기가 $n$ 이라고 한다면 이 알고리즘의 시간복잡도를 Big-Oh notation을 이용하요 나타낸다면  $O(n)$ 이 되겠죠.

그렇지만 이것보다 훨씬 빠르게 target 을 찾아내는 방법도 있습니다. 우리가 살펴봐야 할 요소들의 개수를 절반으로 줄여가면서 탐색을 하는 것이죠. 이런식으로 탐색하는 방법이 바로 이진 탐색 알고리즘입니다. 다만 이진 탐색(binary search)은 오름 차순으로 정렬된 배열에만 적용할 수 있다는 단점이 있습니다. (앞으로 내용을 보시면 아시겠지만 오름차순으로 정렬되지 않은 배열에는 이진 탐색 알고리즘을 적용할 수 없습니다.)

크기가 $n$ 인 리스트 data에서 target 이라는 특정 요소를 찾아낸다고 가정했을 때, 이진 탐색의 절차는 다음과 같습니다.

1. low = $0$, high = $n-1$ 로 초기화 합니다.

2. mid 는 (log + high) 를 2 로 나눈 몫으로 결정합니다.

3.  data[mid] 와 target 이 서로 같으면 목적을 달성했으므로 탐색을 종료합니다.

4. 만약 target < data[mid] 이면 high = mid-1 로 업데이트 한 후, 2번으로 돌아갑니다. 만약 target > data[mid] 라면 low = mid+1 로 업데이트 한 후, 2번으로 돌아갑니다.

위 과정을 보면 low, high, mid 의 값은 요소가 갖는 값들이 아니라 인덱스인 것을 알 수 있습니다. 또한 target 과 data[mid] 의 대소관계에 따라 다음 탐색 방향을 왼쪽 반을 선택할 것인지 오른쪽 반을 선택할 것인지를 결정하기 때문에, 반드시 배열은 오름 차순으로 정렬되어 있어야 합니다.

백문이 불여일견(상황에 맞는 말인가?)이라 예제를 하나 보도록 하겠습니다.

다음과 같은 배열 data 가 있습니다. 여기서는 파이썬의 리스트라고 해 보죠. 여기서 우리는 target=22 를 찾아야 합니다.

배열의 크기가 16 이므로 먼저 low=0, high=15 로 초기화 합니다.

그러면 mid 는 0+15 를 2로 나눈 몫이므로 mid = 7 이 됩니다.

이제 target=22 와 data[7] 을 비교합니다. 

22 = target > data[7] = 14 이므로 (즉, 찾고자 하는 값이 data[7] 보다 오른쪽에 있으므로) low=7+1=8 로 업데이트 해줍니다. 

이것은 곧 mid 에 의해서 둘로 나뉘어진 배열의 조각 중 오른쪽 조각 즉, 인덱스 8~15 까지의 조각에 대해서만 탐색을 하겠다는 의미가 됩니다.

이제 다시 2번으로 돌아가서 mid 값을 업데이트 합니다. 

현재 low=8, high=15 이므로 새로운 mid 의 값은 8+15 를 2로 나눈 몫 11 이 됩니다. 

이번에도 역시 target=22 와 data[11] 을 비교합니다.

22 = target < data[11] = 25 이므로 (즉, 찾고자 하는 값이 data[11] 보다 왼쪽에 있으므로) high=11-1=10 으로 업데이트 해줍니다.

이것은 인덱스 8~15 까지의 조각을 다시 둘로 나눈 왼쪽 조각 즉, 인덱스 8~10까지의 조각에 대해서만 탐색을 하겠다는 의미가 됩니다.

이제 다시 2번으로 돌아가서 mid 의 값을 업데이트 합니다.

현재 low=8, high=10 이므로 새로운 mid의 값은 8+10 을 2로 나눈 몫 9 가 됩니다.

 이제 target=22 와 data[9]를 비교합니다.

22 = target > data[9] = 19 이므로 (즉, 찾고자 하는 값이 data[9] 보다 오른쪽에 있으므로) low=9+1=10 으로 업데이트 해줍니다.

이것은 인덱스 8~10까지의 조각을 다시 둘로 나눈 오른쪽 조각 즉, 인덱스 10~10까지의 조각에 대해서만 탐색을 진행하겠다는 의미가 됩니다.

이제 다시 2번으로 돌아가서 mid 의 값을 업데이트 합니다.

현재 low와 high의 값이 모두 10이므로 mid 역시 10이 됩니다.

이제 target=22 와 data[10]이 서로 같은 값을 갖게 되었으므로 목적이 달성되었고, 탐색을 종료하게 됩니다.

이처럼 이진 탐색은 탐색해야 되는 대상을 절반으로 나누어 가면서 탐색을 진행하기 때문에 $n$ 개의 요소와 target 를 하나씩 비교하는 sequential search 보다 훨씬 빠르게  target 을 찾을 수 있다. 예에서 처럼 배열의 길이가 16이었다면 아래와 같이 단 4회의 탐색으로 target 을 찾아낼 수 있는 것이다. 

물론 이것은 최악의 경우라도 4회 탐색 후에는 target 을 찾아낼 수 있다는 것이다. 만약 target 이 19 였다면 3회의 탐색만으로도 target 을 찾아내는 것이 가능하다.

이것을 좀 더 일반적으로 표현하면 다음과 같다. 

위의 예에서 봤듯이 탐색 대상을 절반으로 줄여 나간다는 것이 정확하게 절반을 보겠다는 것은 아니지만 대충 생각을 해보면 $k$ 번 탐색을 하고 나면 우리가 탐색해야 할 대상의 수는 $\left ( \dfrac{1}{2} \right )^k \times n$ 으로 줄어들게 된다는 것을 알 수 있다. 따라서 최악의 경우 $\left ( \dfrac{1}{2} \right )^k \times n \approx 1$ 이 될때까지 탐색을 해야 target 을 찾을 수 있게 된다. 이때, $\left ( \dfrac{1}{2} \right )^k \times n = 1$ 을 만족하는 $k$ 를 구하기 위해 양변에 $2^k$ 을 곱해주면 $n=2^k$ 이 되고, 다시 양변에 밑이 $2$인 로그를 위해주면  $k=\log_2 n$ 이 되는 것을 알 수 있다, 이것은 곧 최악의 상황이라도 $\log_2 n$ 번의 탐색과정을 거치면 target 을 찾아낼 수 있다는 것을 의미한다. 따라서 이진 탐색 알고리즘의 시간복잡도를 Big-Oh 로 표현하면 $O(\log n)$ 이 된다. 

다음은 이진 탐색을 구현한 파이썬 코드이다. 코드에서 재귀함수가 사용 되었음에 주목할 필요가 있다. 이진 탐색은 재귀함수를 이용하는 알고리즘이다.

def binary_search(data, target, low, high):
    if low > high:
        return false
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid - 1)
        else:
            return binary_search(data, target, mid + 1, high)