반열린 구간으로 첫 이진 탐색 만들기

종이 사전에서 단어를 찾을 때 첫 쪽부터 넘기는 사람은 없습니다. 대충 가운데를 펼쳐 찾는 단어가 앞쪽에 있는지 뒤쪽에 있는지 보고, 남은 절반에서 같은 일을 되풀이합니다. 단어가 가나다순으로 정렬되어 있기 때문에 한 번 펼쳐 보는 것만으로 절반을 통째로 버릴 수 있는 것입니다. 이 방법을 이진 탐색(binary search)이라 하며, 입력 크기·O·Ω·Θ와 정보의 개수에서 본 것처럼 후보 1,000개도 열 번의 비교로 끝납니다. 생각은 단순하지만 정확하게 구현하기는 의외로 어려워서, 구간의 끝을 하나 잘못 옮기면 답을 놓치거나 반복이 끝나지 않습니다. 이 글에서는 같은 값이 여러 번 나오는 정렬된 리스트에서 목표가 처음 나타나는 위치를 찾는 이진 탐색을 만들고, 그 코드가 왜 맞고 왜 끝나는지를 차례로 설명합니다.

정렬되어 있으면 절반을 버릴 수 있다

오름차순으로 정렬된 리스트 values에서 목표 target을 찾는다고 합시다. 가운데 위치 mid의 값을 보고 values[mid] < target이면, 정렬되어 있으므로 mid와 그 왼쪽의 값은 모두 target보다 작습니다. 따라서 target은 mid보다 오른쪽에만 있을 수 있고, 왼쪽 절반은 더 볼 필요가 없습니다. 반대로 values[mid] ≥ target이면 mid부터 오른쪽의 값은 모두 target 이상이므로, target이 처음 나타나는 위치는 mid이거나 그 왼쪽입니다.

두 번째 경우에 values[mid]가 target과 같더라도 바로 멈추지 않는다는 점에 주의해야 합니다. [2, 4, 4, 7, 9]에서 4를 찾을 때 처음 보는 가운데 값은 인덱스 2의 4이지만, 그 왼쪽인 인덱스 1에도 4가 있습니다. 같은 값이 여러 개일 때 아무 위치나 돌려주면 "4점을 받은 첫 학생은 누구인가"나 "4보다 작은 값은 몇 개인가" 같은 질문에 답할 수 없습니다. 그래서 이 글의 이진 탐색은 target이 처음 나타나는 위치를 돌려주고, target이 없으면 -1을 돌려주도록 정합니다. 입력이 정렬되어 있지 않으면 위의 추론이 성립하지 않으므로, 정렬된 입력만 받는다는 것도 이 함수의 사용 조건입니다.

후보 구간을 반열린 구간으로 적는다

탐색하는 동안 아직 버리지 않은 위치들을 두 변수로 나타냅니다. lo는 구간의 왼쪽 끝으로 구간에 포함되고, hi는 오른쪽 끝으로 구간에 포함되지 않습니다. 이렇게 시작은 포함하고 끝은 빼는 구간을 반열린 구간(half-open interval)이라 하고 [lo, hi)로 적습니다. 변수·조건·반복으로 상태 읽기의 range(lo, hi)나 리스트·배열·문자열·딕셔너리의 역할의 슬라이스 values[lo:hi]와 같은 방식입니다.

반열린 구간을 쓰면 몇 가지가 간단해집니다. 구간에 든 위치의 개수가 hi - lo로 바로 나오고, lo와 hi가 같으면 빈 구간입니다. 처음에는 리스트 전체인 lo = 0, hi = len(values)로 시작하는데, 빈 리스트라면 [0, 0)이 되어 따로 처리하지 않아도 됩니다. 또 target이 모든 값보다 커서 target 이상인 첫 위치가 리스트의 끝 바깥인 len(values)가 되는 경우도, hi가 원래 끝 바깥을 가리키므로 자연스럽게 나타낼 수 있습니다.

한 번의 비교로 구간을 줄인다

구간이 비어 있지 않은 동안, 곧 lo < hi인 동안 다음을 되풀이합니다. 가운데 위치를 mid = (lo + hi) // 2로 정하면 lo <= mid < hi이므로 mid는 언제나 구간 안의 위치입니다. values[mid] < target이면 mid까지는 답이 될 수 없으므로 lo = mid + 1로 왼쪽 끝을 mid 다음으로 옮깁니다. 그렇지 않으면 mid가 답일 수도 있으므로 hi = mid로 오른쪽 끝을 mid로 옮깁니다. hi는 구간에 포함되지 않으므로 mid는 이제 검사할 구간에서 빠지지만, 답의 후보로는 hi 자리에 남아 있습니다.

[2, 4, 4, 7, 9]에서 4를 찾는 과정을 단계별로 따라가 보겠습니다.

1단계에서 인덱스 2의 4를 만났지만 hi = 2로 오른쪽 끝만 옮기고 계속합니다. 그 왼쪽에 더 이른 4가 있는지 아직 모르기 때문입니다. 2단계에서 인덱스 1의 4를 만나 다시 hi = 1이 되고, 3단계에서 인덱스 0의 2가 4보다 작으므로 lo = 1이 됩니다. 이제 lo와 hi가 모두 1이라 구간이 비었고 반복이 끝납니다. 멈춘 자리 1의 값이 4이므로 1을 돌려줍니다.

코드로 옮기기

앞의 규칙을 그대로 옮기면 다음과 같습니다. 반복이 끝난 뒤에는 멈춘 자리의 값이 target과 같은지 확인해 답을 정합니다.

def binary_search_first(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if lo < len(values) and values[lo] == target:
        return lo
    return -1


values = [2, 4, 4, 7, 9]
print(binary_search_first(values, 4))
print(binary_search_first(values, 6))
print(binary_search_first(values, 10))
print(binary_search_first([], 4))
print(binary_search_first([4, 4], 4))

1
-1
-1
-1
0

마지막 확인은 두 부분으로 되어 있습니다. lo < len(values)는 target이 모든 값보다 커서 lo가 리스트의 끝 바깥까지 간 경우를 걸러 냅니다. 이 확인이 없으면 세 번째 호출에서 반복이 lo = 5에서 끝난 뒤 values[5]를 읽다가 IndexError가 납니다. 확인이 있을 때 values[5]를 읽지 않는 것은 and가 왼쪽 조건이 거짓이면 오른쪽 조건을 계산하지 않고 바로 거짓이 되기 때문입니다. 그래서 두 조건의 순서를 바꾸면 같은 IndexError가 납니다. values[lo] == target은 멈춘 자리의 값이 target 이상인 첫 값일 뿐이라서 target과 같은지는 따로 확인해야 하기 때문에 필요합니다. 두 번째 호출은 lo = 3에서 멈추지만 그 자리의 값이 7이라서 -1을 돌려줍니다.

왜 맞는가: 반복 내내 참인 두 사실

이 코드가 맞는 이유는 반복하는 동안 늘 참인 두 사실, 곧 불변조건(invariant)으로 설명할 수 있습니다.

1. lo보다 왼쪽 위치의 값은 모두 target보다 작다.
2. hi와 그 오른쪽 위치의 값은 모두 target 이상이다.

처음에는 lo = 0, hi = len(values)라서 lo의 왼쪽에도 hi부터 오른쪽에도 위치가 하나도 없으므로 두 사실이 성립합니다. 반복 한 번이 두 사실을 깨지 않는다는 것도 확인할 수 있습니다. values[mid] < target이면 정렬되어 있으므로 mid와 그 왼쪽의 값이 모두 target보다 작고, 그래서 lo를 mid + 1로 옮겨도 1번이 지켜집니다. 그렇지 않으면 values[mid] ≥ target이고, 정렬되어 있으므로 mid부터 오른쪽의 값이 모두 target 이상이라서 hi를 mid로 옮겨도 2번이 지켜집니다.

반복이 끝나면 lo = hi입니다. 두 사실을 합치면 lo의 왼쪽은 모두 target보다 작고 lo부터는 모두 target 이상이므로, lo는 target 이상인 값이 처음 나타나는 위치입니다. target이 리스트에 있다면 그 첫 위치가 바로 여기이고, 없다면 이 자리의 값은 target보다 크거나 이 자리가 리스트 바깥입니다. 그래서 마지막에 이 자리의 값이 target과 같은지만 확인하면 됩니다. 불변조건·종료와 반례 찾기에서 유클리드 알고리즘을 증명한 것과 같은 방식입니다.

왜 끝나는가: 구간 길이가 절반 이하로 준다

lo < hi인 동안 mid는 lo <= mid < hi를 만족합니다. lo = mid + 1이면 lo가 적어도 1 늘고, hi = mid이면 hi가 적어도 1 줄므로, 구간 길이 hi - lo는 반복마다 줄어듭니다. 길이는 0보다 작아질 수 없으므로 반복은 끝납니다. 또 lo = mid + 1은 hi를 넘지 않고 hi = mid는 lo보다 작지 않으므로, 끝났을 때는 lo > hi가 아니라 정확히 lo = hi입니다.

줄어드는 양도 따져 볼 수 있습니다. 길이가 L인 구간에서 mid - lo는 L // 2이고 hi - (mid + 1)은 그보다 크지 않으므로, 어느 쪽으로 가든 새 길이는 L // 2 이하입니다. 예제에서 길이가 5, 2, 1, 0으로 줄어 반복이 세 번이었던 것도 이 때문입니다. 일반적으로 길이 n에서 시작하면 반복은 많아야 ⌊log₂ n⌋ + 1번입니다. ⌊x⌋는 x 이하의 정수 가운데 가장 큰 것을 뜻하는 바닥 함수라서, n이 1,000이면 log₂ 1000 ≈ 9.97을 내린 9에 1을 더한 10번입니다.

비용과 쓰임

반복마다 비교를 한 번 하므로 비교 횟수는 O(log n)이고, 변수 몇 개 외에 추가 공간은 O(1)입니다. 순차 탐색의 O(n)과는 차이가 매우 크지만, 정렬된 입력이 있어야 한다는 조건이 붙습니다. 정렬되지 않은 리스트에서 한 번만 찾는다면 순차 탐색이 낫습니다. 정렬에 O(n log n)이 들어 그 자체가 순차 탐색보다 비싸기 때문입니다. 같은 리스트에서 여러 번 찾는다면 한 번 정렬해 두고 매번 이진 탐색을 쓰는 편이 유리합니다.

Python 표준 라이브러리의 bisect 모듈에는 같은 일을 하는 함수가 있습니다. bisect_left(values, target)은 우리 함수의 반복이 끝났을 때의 lo, 곧 target 이상인 값이 처음 나타나는 위치를 돌려줍니다. bisect_right는 target보다 큰 값이 처음 나타나는 위치를 돌려주므로, 둘의 차이가 target의 개수입니다.

from bisect import bisect_left, bisect_right

values = [2, 4, 4, 7, 9]
for target in [4, 6, 10]:
    print(target, bisect_left(values, target), bisect_right(values, target))
print(bisect_right(values, 4) - bisect_left(values, 4))

4 1 3
6 3 3
10 5 5
2

bisect_left는 target이 없어도 -1 대신 끼워 넣을 위치를 돌려준다는 점이 우리 함수와 다릅니다. 6에 대한 3은 6을 인덱스 3에 넣으면 정렬이 유지된다는 뜻이라서, 정렬된 리스트에 새 값을 넣을 자리를 찾을 때도 이 함수를 씁니다.

더 깊이: 이진 탐색이 틀리기 쉬운 이유

이진 탐색은 설명은 짧지만 정확히 구현하기 어렵기로 유명합니다. Jon Bentley는 『Programming Pearls』에서 숙련된 프로그래머들에게 이진 탐색을 짜게 했더니 약 90%가 자신의 코드에서 버그를 발견했다고 적었습니다. 구간을 닫힌 구간 [lo, hi]로 잡을지 반열린 구간으로 잡을지에 따라 초깃값, 반복 조건, 갱신식이 모두 달라지는데, 이것들은 한 벌로 맞물려 있어서 하나만 다른 방식으로 바꾸면 코드가 틀어집니다.

본문 코드에서 반복 조건만 닫힌 구간에서 쓰는 lo <= hi로 바꿔 보면 알 수 있습니다. [2]에서 5를 찾으면 lo = hi = 1일 때도 반복이 계속되어 mid가 1이 되고, 리스트 바깥의 values[1]을 읽다가 IndexError가 납니다. [4]에서 4를 찾으면 lo = hi = 0에서 hi = mid가 구간을 줄이지 못해 반복이 끝나지 않습니다. 구간을 어떻게 나타낼지 먼저 정하고, 불변조건에 맞춰 초깃값·반복 조건·갱신식을 한꺼번에 정하는 습관이 이런 실수를 막아 줍니다.

언어에 따라서는 가운데 위치를 구하는 식 자체가 문제가 되기도 합니다. Java나 C처럼 정수의 크기가 정해진 언어에서는 lo + hi가 표현할 수 있는 가장 큰 정수를 넘을 수 있고, 32비트 정수라면 원소가 약 10억 개를 넘는 배열에서 이런 일이 생길 수 있습니다. 이런 부호 있는 넘침이 일어나면 Java에서는 합이 엉뚱한 음수가 되고, C에서는 동작이 정해져 있지 않아 결과를 예측할 수 없습니다. Joshua Bloch는 2006년에 Java 표준 라이브러리의 이진 탐색에 이 버그가 9년가량 숨어 있었다는 사실을 알렸습니다. 가운데를 lo + (hi - lo) / 2처럼 구하면 중간 계산이 hi를 넘지 않아 이 문제를 피할 수 있습니다. Python의 정수는 크기 제한이 없으므로 (lo + hi) // 2를 그대로 써도 됩니다.

정리

• 정렬된 리스트에서는 가운데 값과 target을 한 번 비교해 후보의 절반을 버릴 수 있습니다.
• 후보 구간을 반열린 구간 [lo, hi)로 나타내면 길이가 hi - lo이고, lo = hi가 빈 구간이며, 답이 리스트 끝 바깥인 경우도 나타낼 수 있습니다.
• values[mid] < target이면 lo = mid + 1, 그렇지 않으면 hi = mid로 옮깁니다. 같은 값을 만나도 멈추지 않아야 첫 위치를 찾습니다.
• lo 왼쪽은 target보다 작고 hi부터는 target 이상이라는 불변조건이 정확성을, 반복마다 줄어드는 구간 길이가 종료를 설명합니다.
• 반복은 많아야 ⌊log₂ n⌋ + 1번이라 비교 횟수가 O(log n)입니다. 정렬 비용까지 생각해 순차 탐색과 견주어 고릅니다.

연습 문제

1. 있는 값과 없는 값 추적하기

[1, 3, 3, 3, 8, 10]에서 3과 9를 각각 찾을 때 (lo, hi, mid)가 어떻게 바뀌는지 끝까지 추적하고, 함수가 돌려주는 값을 구하세요.

2. lo = mid로 바꾸면

lo = mid + 1을 lo = mid로 바꾸면 [1]에서 5를 찾을 때 어떤 일이 생길까요?

def first_with_bug(values, target, limit):
    lo, hi = 0, len(values)
    steps = 0
    while lo < hi and steps < limit:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid
        else:
            hi = mid
        steps += 1
    return lo, hi, steps


print(first_with_bug([1], 5, 100))

(0, 1, 100)

3. 정렬되지 않은 입력

binary_search_first([9, 1, 7], 7)은 2를 돌려주어 맞는 답이 나옵니다. 그렇다면 정렬되지 않은 입력에도 이 함수를 써도 될까요? 같은 리스트에서 9를 찾아 확인해 보세요.

def binary_search_first(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = (lo + hi) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    if lo < len(values) and values[lo] == target:
        return lo
    return -1


print(binary_search_first([9, 1, 7], 7))
print(binary_search_first([9, 1, 7], 9))

2
-1

다음 장의 버블·선택 정렬에서는 이진 탐색이 기대는 정렬된 입력을 직접 만드는 방법부터 시작합니다.