이진 탐색: 반씩 잘라 찾기
정렬된 칸 16개에서 값 하나를 찾습니다. 가운데 칸 하나만 보고 절반을 버리기를 되풀이하면 많아야 5번이면 끝납니다. 칸이 100만 개여도 20번입니다. 한 걸음씩 넘기며 남은 구간이 어떻게 줄어드는지 보세요.
한 줄 답. 이진 탐색은 정렬된 배열에서 가운데 칸을 보고, 찾는 값이 더 작으면 오른쪽 반을, 더 크면 왼쪽 반을 버리기를 되풀이하는 찾기입니다. 한 번 볼 때마다 남은 칸이 반으로 줄어서, 칸이 n 개면 많아야 ⌊log₂ n⌋ + 1 번 봅니다(100만 칸이면 20번). 값 대신 「조건이 처음 참이 되는 자리」를 찾는 데도 똑같이 씁니다. Python 의 bisect 가 그것입니다.
칸 안의 수가 값, 칸 밑 작은 수가 칸 번호입니다. 비교 한 번은 세 걸음입니다. 가운데를 고르면 칸 위에 주황 화살표 mid 가 섭니다. 비교하면 그 위에 가운데 값과 찾는 값의 크기 기호가 붙습니다(처음은 31 < 44). 반을 버리면 버린 칸 위에 「버림」 괄호가 붙고, 옮겨 간 lo 나 hi 는 흐린 옛 자리에서 새 자리로 화살표가 갑니다. 칸 아래 파란 화살표가 lo 와 hi 이고, 같은 칸을 가리키면 옆으로 나란히 섭니다. 초록 칸이 아직 남은 구간(lo ~ hi), 회색에 줄이 그어진 칸이 버린 쪽, 점선 칸은 배열 밖 자리입니다. 찾으면 그 칸이 진한 초록이 됩니다. 「(배열에 없음)」이 붙은 값을 고르면 어디서 멈추는지 볼 수 있습니다. 값은 지어낸 16개입니다.
1. 이진 탐색이란: 정렬돼 있어야 한다
종이 사전에서 낱말을 찾을 때 첫 쪽부터 넘기지 않습니다. 가운데쯤을 펴고, 찾는 낱말이 그보다 앞이면 앞쪽 절반만, 뒤면 뒤쪽 절반만 남깁니다. 남은 쪽에서 또 가운데를 폅니다. 이진 탐색은 이것을 배열에 그대로 한 것입니다.
이것이 되는 까닭은 정렬입니다. 작은 것부터 늘어놓았으니 가운데 칸의 왼쪽은 모두 그 값보다 작거나 같고, 오른쪽은 모두 크거나 같습니다. 그래서 가운데 값 하나만 보고 한쪽 절반 전체에 답이 없다고 말할 수 있습니다. 정렬이 깨진 배열에 쓰면 답이 있는 쪽을 버릴 수 있고, 오류 없이 「없음」 같은 틀린 답을 냅니다.
또 하나, 가운데 칸으로 한 번에 갈 수 있어야 합니다. 번호로 바로 가는(임의 접근, random access) 배열이어야 하고, 앞에서부터 따라가야 하는 연결 리스트에서는 이득이 없습니다(자주 묻는 것 3).
2. 절차
남은 구간의 왼쪽 끝을 lo, 오른쪽 끝을 hi, 가운데를 mid 라고 부릅니다. 실험 ① 은 양 끝 칸을 모두 구간에 넣는 방식입니다(닫힌 구간).
lo = 0,hi = n − 1. 찾는 값이 있다면 칸 lo ~ hi 안에 있습니다.lo ≤ hi인 동안 되풀이합니다.mid = lo + (hi − lo) // 2((lo + hi) // 2와 같은 값).a[mid]가 찾는 값과 같으면 mid 를 돌려주고 끝납니다.- 찾는 값이 더 작으면
hi = mid − 1. mid 와 그 오른쪽을 버립니다. - 찾는 값이 더 크면
lo = mid + 1. mid 와 그 왼쪽을 버립니다. lo > hi가 되면 남은 칸이 없으니 「없음」입니다. 이때lo는 그 값을 넣어도 정렬이 깨지지 않는 자리입니다.
알고리즘 교과서 『Algorithms』 1.1 절의 BinarySearch 가 이 짜임입니다. lo 와 hi 를 두고 「찾는 값이 있다면 a[lo..hi] 안에 있다」를 걸음마다 지키다가, 없으면 −1 을 돌려줍니다.
해 볼 것. ① 처음 값 44 는 비교 4번 만에 칸 10 에서 찾습니다. ② 31 을 고르면 첫 가운데 칸(7)이라 1번에 끝납니다. 75 는 5번이고, 16칸에서는 이보다 많은 경우가 없습니다. 있는 값 16개를 하나씩 찾으면 평균 3.38번입니다. ③ 20(배열에 없음)을 고르면 비교 4번 뒤 lo = 5, hi = 4 로 엇갈려 멈춥니다. 칸 5 는 19 와 23 사이, 20 이 들어갈 자리(삽입 위치, insertion point)입니다. ④ 80 을 고르면 lo = 16, 마지막 칸 다음에서 멈춥니다.
3. 손으로 따라가기
배열은 실험 ① 과 같습니다: 3, 7, 12, 15, 19, 23, 28, 31, 36, 40, 44, 51, 57, 62, 68, 75(칸 0 ~ 15). 먼저 있는 값 44 를 찾습니다.
| 비교 | lo | hi | mid | a[mid] | 비교 결과 | 다음 | 왜 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 15 | 7 | 31 | 44 > 31 | lo = 8 | 칸 0 ~ 7 은 모두 31 이하 |
| 2 | 8 | 15 | 11 | 51 | 44 < 51 | hi = 10 | 칸 11 ~ 15 는 모두 51 이상 |
| 3 | 8 | 10 | 9 | 40 | 44 > 40 | lo = 10 | 칸 8 ~ 9 는 모두 40 이하 |
| 4 | 10 | 10 | 10 | 44 | 같다 | 칸 10 을 돌려준다 | 찾는 값과 같다 |
다음은 없는 값 20 입니다.
| 비교 | lo | hi | mid | a[mid] | 비교 결과 | 다음 | 왜 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 15 | 7 | 31 | 20 < 31 | hi = 6 | 칸 7 ~ 15 는 모두 31 이상 |
| 2 | 0 | 6 | 3 | 15 | 20 > 15 | lo = 4 | 칸 0 ~ 3 은 모두 15 이하 |
| 3 | 4 | 6 | 5 | 23 | 20 < 23 | hi = 4 | 칸 5 ~ 6 은 모두 23 이상 |
| 4 | 4 | 4 | 4 | 19 | 20 > 19 | lo = 5 | 칸 4 는 19 |
| 끝 | 5 | 4 | − | − | lo > hi | 없음. 들어갈 자리는 칸 5 | 남은 칸이 없다 |
실험 ① 은 비교 한 번을 고름, 비교, 버림의 세 걸음으로 나눠 보여 줍니다. 그래서 44 는 걸음 11개, 20 은 걸음 13개(마지막 「lo > hi」 걸음 포함)입니다.
두 경우 모두 4번 봤습니다. 없는 값에서 멈출 때 lo 는 늘 「찾는 값보다 작은 값의 개수」와 같습니다. 20 보다 작은 값은 3, 7, 12, 15, 19 다섯 개라 lo = 5 입니다.
4. 왜 log₂ n 번인가
한 번 볼 때마다 남은 칸이 반(이하)으로 줄어듭니다. 16칸이면 16 → 8 → 4 → 2 → 1. 네 번 반으로 나누면 한 칸이 남고, 그 한 칸까지 보면 많아야 5번입니다. n 을 1 이 될 때까지 반으로 나누는 횟수가 log₂ n 이라서, 칸이 n 개면 많아야 ⌊log₂ n⌋ + 1 번 봅니다.
100만 칸이면 1,000,000 → 500,000 → 250,000 → … 으로 20번 나누면 1 보다 작아집니다(2²⁰ = 1,048,576). 그래서 많아야 20번입니다. 이 쪽의 코드로 0 ~ 999,999 를 담은 배열에서 재 봐도 가장 많이 20번입니다. 앞에서부터 하나씩 보면 많아야 1,000,000 번입니다. 칸이 두 배가 되어도 이진 탐색은 한 번만 더 보면 됩니다. 이것을 O(log n), 로그 시간이라고 부릅니다(시간 복잡도).
5. 값이 아니라 조건으로 찾기: bisect_left 와 bisect_right
같은 값이 여러 개면 실험 ① 의 방식은 그 가운데 아무 칸에서나 멈춥니다. 아래 배열에서 5 를 찾으면 첫 가운데 칸 7 이 마침 5 라서 바로 멈춥니다. 5 가 처음 나오는 칸은 3 인데도 그렇습니다.
그래서 질문을 바꿉니다. 칸마다 「a[i] ≥ x 인가?」를 묻습니다. 배열이 정렬돼 있으면 답이 거짓, 거짓, …, 거짓, 참, 참, …, 참 처럼 딱 한 번만 바뀝니다. 찾는 것은 처음으로 참이 되는 자리, 곧 거짓과 참의 경계입니다.
- 구간은
[lo, hi): lo 는 넣고 hi 는 뺍니다(반열린 구간, half-open interval). 처음은lo = 0,hi = n. 참이 되는 칸이 하나도 없으면 답은 n(끝 다음)입니다. - 가운데가 참이면 답은 mid 이거나 그 왼쪽입니다. mid 를 버리지 않고
hi = mid. - 가운데가 거짓이면 답은 mid 보다 오른쪽입니다.
lo = mid + 1. lo == hi가 되면 끝. 그 자리가 답입니다. 값이 같은지는 한 번도 묻지 않습니다.
조건을 a[i] ≥ x 로 두면 맨 왼쪽 x 의 자리인 하한(lower bound, bisect_left), a[i] > x 로 두면 맨 오른쪽 x 의 다음 자리인 상한(upper bound, bisect_right)이 나옵니다. 둘의 차가 x 의 개수입니다. x 가 없으면 둘 다 x 가 들어갈 자리를 가리킵니다.
칸 밑 작은 수는 칸 번호, 그 아래 T·F 는 칸마다 조건이 참(T)인지 거짓(F)인지입니다. 찾는 것은 F 가 T 로 바뀌는 경계입니다. 걸음은 실험 ① 처럼 고름, 물음, 버림 셋이고, 물을 때는 가운데 칸 위에 8 ≥ 5 참 같은 글이 붙습니다. 구간에서 빠지는 hi 는 남은 구간 바로 오른쪽 칸을 가리킵니다(처음에는 끝 다음의 점선 칸). 가운데가 참이면 hi 가 가운데 칸으로 옮겨 가고, 그 칸은 「버림」 괄호 밖에 남습니다. 마지막 걸음에서 답의 칸이 진한 초록이 됩니다.
해 볼 것. ① 처음(x = 5, bisect_left)은 비교 4번 뒤 lo = hi = 3 에서 멈춥니다. 5 가 처음 나오는 칸입니다. ② bisect_right 를 누르면 역시 4번 뒤 8 입니다. 8 − 3 = 5, 배열에 5 가 다섯 개 있습니다. ③ x = 6(없는 값)은 둘 다 8 이라 차가 0 입니다. 8 은 6 이 들어갈 자리입니다. ④ x = 21 은 둘 다 16, 끝 다음입니다. ⑤ x = 0 은 모든 칸이 T 라 hi 만 왼쪽으로 와서 0 에서 멈춥니다(비교 5번).
이 틀은 배열이 아니어도 됩니다. 「어느 자리부터 쭉 참」인 조건(단조 조건, monotone predicate)이면 그 경계를 같은 방법으로 찾습니다. 아래 「어디에 쓰나」의 git bisect 가 그 예입니다.
6. 흔한 실수
- 구간 끝을 넣느냐 빼느냐를 섞는다. 닫힌 구간
[lo, hi]는hi = n − 1,while lo <= hi,hi = mid − 1이 한 벌입니다. 반열린 구간[lo, hi)는hi = n,while lo < hi,hi = mid가 한 벌입니다. 섞으면 마지막 칸을 보지 못하거나 배열 밖(a[n])을 읽습니다. - 끝나는 조건이 하나 모자란다. 닫힌 구간에서
while lo < hi로 쓰면 lo = hi 인 마지막 한 칸을 보지 않고 끝납니다. 손으로 따라가기에서 44 는 4번째 비교(lo = hi = 10)에서 찾았으니, 이 실수로는 「없음」이 나옵니다. - 끝없이 돈다.
lo = mid + 1대신lo = mid로 쓰면, 구간이 두 칸(hi = lo + 1)일 때 mid = lo 라서 lo 가 그대로이고 같은 걸음을 영원히 되풀이합니다. 걸음마다 구간이 적어도 한 칸 줄어드는지 보면 막을 수 있습니다. - 정렬 안 된 배열에 쓴다. 오류가 나지 않고 틀린 답이 나와서 알아채기 어렵습니다.
7. 꼭 알아야 할 성질
| 성질 | 쉬운 말 | 실험에서 |
|---|---|---|
| 정렬이 먼저 | 가운데 값 하나로 반을 버릴 수 있는 까닭이 정렬이다 | 배열이 작은 것부터 놓여 있다 |
| 걸음마다 반 | n 칸이면 많아야 ⌊log₂ n⌋ + 1 번. 칸이 두 배면 한 번 더 | 16칸은 많아야 5번(75) |
| 없으면 삽입 위치를 안다 | 멈춘 lo 가 정렬을 지키며 넣을 자리 | 20 → 칸 5 |
| 같은 값이 여럿이면 어느 칸인지 정해져 있지 않다 | 맨 왼쪽·맨 오른쪽 다음은 조건으로 찾는다 | ② 의 5: 칸 3 과 8 |
| 번호로 바로 가야 한다 | 가운데 칸으로 한 번에 가는 배열에서만 빠르다 | − |
8. 언제 무엇을 쓰나
| 방법 | 찾기: 최선 · 평균 · 최악 | 더 드는 메모리 | 좋은 점 | 나쁜 점 | 쓰는 경우 |
|---|---|---|---|---|---|
| 앞에서부터 하나씩 찾는 선형 탐색(linear search) | 1번 · n/2 번쯤 · n 번. n 이 두 배면 두 배(O(n)) | 없음 | 정렬이 필요 없다. 짧다 | 칸이 많으면 느리다 | 작은 자료, 한 번만 찾을 때, 정렬 안 된 자료 |
| 이진 탐색(정렬된 배열) | 1번 · log₂ n 번쯤 · ⌊log₂ n⌋ + 1 번. n 이 두 배면 한 번 더(O(log n)) | 없음 | 빠르다. 범위(a 이상 b 미만)와 「처음 참이 되는 자리」도 찾는다 | 정렬해 둬야 한다. 넣고 빼기는 뒤 칸을 밀어야 해서 O(n) | 잘 바뀌지 않는 자료를 여러 번 찾을 때, 범위 찾기 |
| 해시 테이블 | 1번 · 1번쯤 · n 번(모두 한 칸에 몰릴 때). 보통 O(1) | 빈 칸을 둔 표 | 정확히 같은 키 하나 찾기가 가장 빠르다 | 순서가 없어 범위나 「다음으로 큰 값」을 못 찾는다 | 키로 바로 찾기(Python 의 dict) |
| 이진 탐색 트리 | 1번 · log n 번쯤(무작위 순서로 넣었을 때) · n 번(정렬된 순서로 넣어 한 줄이 됐을 때) | 칸마다 링크 둘 | 넣고 빼면서도 순서를 지킨다 | 한쪽으로 기울면 느리다. 그래서 균형 트리를 쓴다 | 자주 넣고 빼면서 순서도 필요할 때 |
Python 문서도 같은 말을 합니다. 값의 범위를 찾는 데는 이진 탐색이 좋고, 정해진 값 하나를 찾는 데는 딕셔너리가 더 빠르며, insort 는 찾기가 O(log n) 이어도 넣는 단계가 O(n) 이라 전체가 O(n) 입니다.
9. Python 으로
def bisect_left(a, x):
lo, hi = 0, len(a) # 반열린 구간 [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x: # 조건 a[mid] >= x 가 거짓
lo = mid + 1
else:
hi = mid
return lo
a = [3, 7, 12, 15, 19, 23, 28, 31, 36, 40, 44, 51, 57, 62, 68, 75]
i = bisect_left(a, 44)
print(i, i < len(a) and a[i] == 44) # 10 True
표준 라이브러리에 같은 것이 있습니다. 직접 쓰지 말고 이것을 씁니다.
import bisect
bisect.bisect_left(a, 44), bisect.bisect_left(a, 20) # (10, 5): 20 은 없고 칸 5 에 들어간다
r = [1, 3, 3, 5, 5, 5, 5, 5, 8, 8, 11, 13, 13, 13, 16, 20]
bisect.bisect_right(r, 5) - bisect.bisect_left(r, 5) # 5: 5 의 개수
bisect 는 값이 같은지 묻지 않고 「작은가」(<)만 묻습니다. 찾는 값이 있는지는 위처럼 돌려받은 칸을 한 번 더 봐서 정합니다. 문서의 「Searching Sorted Lists」 절에 이렇게 쓰는 함수 다섯 개가 있습니다. Python 3.10 부터는 key= 로 기록의 한 칸을 기준으로 찾을 수 있고, insort 는 찾은 자리에 바로 넣어 줍니다.
어디에 쓰나
- 정렬된 배열에서 찾기와 세기. 있는지, 몇 개인지(bisect_right − bisect_left), 어떤 범위에 몇 개 드는지.
- DB 인덱스의 생각. 인덱스는 키를 정렬된 차례로 들고 있어서, 표 전체를 읽지 않고 범위를 좁혀 가며 찾습니다. 실제 인덱스는 디스크에 맞춘 여러 갈래 나무(B-트리 같은 것)라 이진 탐색과 똑같지는 않지만, 「정렬해 두면 다 보지 않아도 된다」는 생각은 같습니다.
created_at의 범위로 찾는 질의가 빠른 것도 정렬 덕입니다. - 처음 깨진 곳 찾기(git bisect). 잘 되던 커밋과 깨진 커밋을 알려 주면 그 사이 가운데 커밋을 꺼내 줍니다. 시험해서 좋다·나쁘다를 알려 주면 반을 버립니다. 「처음 깨진 커밋」은 「깨졌나」라는 조건이 처음 참이 되는 자리이고, 5절의 방법 그대로입니다. 커밋이 1,000개면 열 번쯤 시험하면 됩니다.
- 답을 반씩 좁히기. 「이 크기면 되나?」가 어느 크기부터 쭉 참이면, 크기 후보 전체를 배열처럼 놓고 되는 가장 작은 크기를 찾습니다.
자주 묻는 것
정렬돼 있지 않으면 먼저 정렬하고 찾으면 되나요?
한 번만 찾을 거면 손해입니다. 정렬에는 n log n 쯤 걸리는데, 선형 탐색은 n 번이면 끝납니다. 같은 자료에서 여러 번 찾을 때 한 번 정렬해 두는 값이 있습니다.
같은 값이 여러 개면 몇 번째 칸을 돌려주나요?
값으로 찾는 방식(실험 ①)은 같은 값들 가운데 가운데 칸으로 먼저 닿은 하나에서 멈춥니다. 어느 칸일지는 배열의 길이와 값의 위치에 따라 달라집니다. 맨 왼쪽 칸이 필요하면 bisect_left 를, 맨 오른쪽 다음 자리가 필요하면 bisect_right 를 씁니다.
연결 리스트에서도 쓸 수 있나요?
이득이 없습니다. 이진 탐색은 가운데 칸으로 한 번에 가야 하는데, 연결 리스트는 앞에서부터 따라가야 가운데에 닿습니다. 가운데로 가는 데만 n/2 걸음이 듭니다. 연결된 구조에서 같은 일을 하려면 이진 탐색 트리를 씁니다.
정렬하는 방법은 기초 정렬과 병합 정렬과 퀵 정렬 쪽에 있습니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 반씩 잘라 찾기 | 이진 탐색, 이분 탐색(binary search) |
| 앞에서부터 하나씩 찾기 | 선형 탐색, 순차 탐색(linear search, sequential search) |
| 남은 구간의 왼쪽 끝, 오른쪽 끝, 가운데 칸 | lo, hi, mid(low, high, middle) |
| 양 끝을 넣는 구간 / 오른쪽 끝을 빼는 구간 | 닫힌 구간 [lo, hi](closed interval) / 반열린 구간 [lo, hi)(half-open interval) |
| 없을 때 들어갈 자리 | 삽입 위치(insertion point) |
| 조건이 처음 참이 되는 자리 | 하한(lower bound, bisect_left), 상한(upper bound, bisect_right) |
| 어느 자리부터 쭉 참인 조건 | 단조 조건(monotone predicate) |
| 번호로 바로 가기 | 임의 접근(random access) |
| 칸이 두 배면 한 번 더 | 로그 시간, O(log n) |
출처
- Python 문서, bisect: Array bisection algorithm. bisect_left·bisect_right 가 돌려주는 삽입 위치의 뜻,
__lt__만 쓴다는 것,key(3.10), insort 의 O(n), 범위에는 이진 탐색·값 하나에는 딕셔너리, Searching Sorted Lists 의 함수들. - Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, 1.1 Programming Model. BinarySearch(lo 와 hi 로 구간을 지키며 가운데와 견주고, 없으면 −1).