정렬된 값들 사이에서 특정 값을 찾는다고 하겠습니다. 앞에서부터 하나씩 확인하면 값이 뒤에 있을수록 오래 걸립니다. 그런데 값이 정렬되어 있다는 조건이 있으면 훨씬 영리하게 찾을 수 있습니다. 가운데를 먼저 보고 찾는 값이 그보다 크면 오른쪽 절반만, 작으면 왼쪽 절반만 남기는 방식입니다. 이렇게 범위를 절반씩 줄여 나가는 탐색을 이진 탐색(binary search)이라고 합니다. 100만 개짜리 목록도 스무 번이면 찾아냅니다. 이번 글에서 그 놀라운 속도를 직접 확인해 보겠습니다.
16.1 이진 탐색 직접 구현하기
이진 탐색의 핵심은 세 개의 위치를 다루는 것입니다. 찾는 범위의 왼쪽 끝 lo, 오른쪽 끝 hi, 그리고 그 가운데 mid입니다. 가운데 값을 찾는 값과 비교해 범위를 절반으로 줄입니다.
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))
print(binary_search(arr, 8))
3
-1
동작을 따라가 보겠습니다. 처음 가운데는 인덱스 3의 값 7입니다. 찾는 값 7과 같으니 바로 인덱스 3을 돌려줍니다. 없는 값 8을 찾을 때는, 가운데 7보다 크니 왼쪽 절반을 버리고 오른쪽만 봅니다. 다시 그 범위의 가운데와 비교하며 좁히다가 결국 lo가 hi를 넘어서면 없다는 뜻이라 -1을 돌려줍니다.
비교할 때마다 후보 범위가 절반으로 줄어드는 것이 핵심입니다. 한 가지 조건을 꼭 기억하세요. 이진 탐색은 반드시 정렬된 리스트에서만 올바르게 동작합니다. 정렬돼 있지 않으면 "왼쪽 절반을 버린다"는 판단 자체가 성립하지 않기 때문입니다. 복잡도는 O(log n)입니다.
16.2 선형 탐색과 비교 횟수 재보기
절반씩 줄이는 것이 얼마나 큰 차이를 만드는지 숫자로 확인해 보겠습니다. 100만 개짜리 정렬 리스트에서 맨 끝 값을 찾을 때, 앞에서부터 하나씩 보는 선형 탐색(linear search)과 이진 탐색이 각각 몇 번 비교하는지 세어 보겠습니다.
def linear_count(a, t):
c = 0
for x in a:
c += 1
if x == t:
return c
return c
def binary_count(a, t):
c = 0; lo, hi = 0, len(a) - 1
while lo <= hi:
c += 1
mid = (lo + hi) // 2
if a[mid] == t: return c
elif a[mid] < t: lo = mid + 1
else: hi = mid - 1
return c
big = list(range(1000000))
print("선형:", linear_count(big, 999999), "번")
print("이진:", binary_count(big, 999999), "번")
선형: 1000000 번
이진: 20 번
선형 탐색은 맨 끝 값을 찾느라 100만 번을 전부 비교했습니다. 이진 탐색은 단 20번입니다. 이것이 O(n)과 O(log n)의 실제 차이입니다. 데이터가 두 배로 늘어도 이진 탐색은 비교가 한 번 더 늘어날 뿐입니다. 100만이 200만이 되어도 21번, 다시 400만이 되어도 22번인 셈입니다. 반씩 줄이는 힘이 이렇게 큽니다.
다만 한 가지 조건을 잊지 마세요. 이진 탐색이 이렇게 빠른 것은 데이터가 이미 정렬돼 있을 때의 이야기입니다. 정렬돼 있지 않다면 먼저 정렬하는 비용이 따로 듭니다. 값을 한 번 찾고 말 거라면 그냥 선형 탐색이 나을 수도 있습니다. 하지만 정렬된 데이터에서 여러 번 되풀이해 찾아야 한다면, 이진 탐색만큼 강력한 도구가 없습니다.
16.3 bisect: 파이썬에 들어 있는 이진 탐색
이진 탐색은 워낙 자주 쓰여서 파이썬 표준 라이브러리에 이미 들어 있습니다. bisect 모듈입니다. 직접 짜지 않아도 "정렬을 유지하며 값을 넣을 자리"를 이진 탐색으로 찾아 줍니다.
import bisect
b = [1, 3, 5, 7, 9]
print(bisect.bisect_left(b, 5)) # 5가 있으면 그 왼쪽 위치
print(bisect.bisect_right(b, 5)) # 5의 오른쪽 위치
print(bisect.bisect_left(b, 6)) # 6을 넣을 자리
2
3
3
bisect_left는 그 값이 들어갈 가장 왼쪽 위치를, bisect_right는 가장 오른쪽 위치를 알려 줍니다. 5는 인덱스 2에 있으므로 그 왼쪽 자리는 2, 오른쪽 자리는 3입니다. 리스트에 없는 6은 5와 7 사이인 인덱스 3에 들어가야 정렬이 유지됩니다. 같은 값이 여러 개일 때 left와 right가 각각 어느 쪽 경계인지 정해 준다는 점이 유용합니다. 두 함수 모두 O(log n)입니다.
16.4 insort: 정렬을 유지하며 끼워 넣기
넣을 자리를 찾는 데서 한발 더 나아가, 실제로 그 자리에 값을 끼워 넣어 주는 함수도 있습니다. bisect의 insort입니다.
import bisect
b = [1, 3, 5, 7, 9]
bisect.insort(b, 6)
print(b)
[1, 3, 5, 6, 7, 9]
insort는 알맞은 자리를 이진 탐색으로 찾아 6을 그 자리에 끼웠습니다. 결과 리스트는 여전히 정렬된 상태입니다. 자리를 찾는 일은 O(log n)으로 빠르지만, 실제로 끼워 넣을 때 뒤의 값들을 한 칸씩 밀어야 하므로 그 부분은 O(n)입니다. 그래도 값을 넣을 때마다 전체를 다시 정렬하는 것보다는 훨씬 낫습니다.
16.5 정리
이진 탐색은 정렬된 데이터에서 범위를 절반씩 줄여 O(log n)에 값을 찾는 방법입니다. 100만 개도 스무 번이면 찾아낼 만큼 빠릅니다. 원리를 이해했다면 실전에서는 직접 짜기보다 표준 라이브러리 bisect를 쓰면 됩니다. 검증되어 있고 오류를 낼 걱정이 없기 때문입니다. bisect_left와 bisect_right로 넣을 자리를 찾고, insort로 정렬을 유지하며 값을 끼워 넣습니다. 잊지 말아야 할 단 하나의 전제는, 이 모든 것이 데이터가 정렬돼 있을 때 성립한다는 점입니다. 이진 탐색을 쓰기 전에 리스트가 정렬돼 있는지부터 확인하는 습관을 들이면, 앞으로 큰 데이터를 다룰 때 큰 힘이 될 것입니다.