이진 탐색: 반씩 잘라 찾기

정렬된 칸 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 라고 부릅니다. 실험 ① 은 양 끝 칸을 모두 구간에 넣는 방식입니다(닫힌 구간).

  1. lo = 0, hi = n − 1. 찾는 값이 있다면 칸 lo ~ hi 안에 있습니다.
  2. lo ≤ hi 인 동안 되풀이합니다. mid = lo + (hi − lo) // 2((lo + hi) // 2 와 같은 값).
  3. a[mid] 가 찾는 값과 같으면 mid 를 돌려주고 끝납니다.
  4. 찾는 값이 더 작으면 hi = mid − 1. mid 와 그 오른쪽을 버립니다.
  5. 찾는 값이 더 크면 lo = mid + 1. mid 와 그 왼쪽을 버립니다.
  6. 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 를 찾습니다.

비교lohimida[mid]비교 결과다음왜
101573144 > 31lo = 8칸 0 ~ 7 은 모두 31 이하
2815115144 < 51hi = 10칸 11 ~ 15 는 모두 51 이상
381094044 > 40lo = 10칸 8 ~ 9 는 모두 40 이하
410101044같다칸 10 을 돌려준다찾는 값과 같다

다음은 없는 값 20 입니다.

비교lohimida[mid]비교 결과다음왜
101573120 < 31hi = 6칸 7 ~ 15 는 모두 31 이상
20631520 > 15lo = 4칸 0 ~ 3 은 모두 15 이하
34652320 < 23hi = 4칸 5 ~ 6 은 모두 23 이상
44441920 > 19lo = 5칸 4 는 19
끝54−−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 인가?」를 묻습니다. 배열이 정렬돼 있으면 답이 거짓, 거짓, …, 거짓, 참, 참, …, 참 처럼 딱 한 번만 바뀝니다. 찾는 것은 처음으로 참이 되는 자리, 곧 거짓과 참의 경계입니다.

조건을 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. 흔한 실수

칸 4 칸 5 lo · mid hi lo = mid → 그대로 4
lo = mid (틀림). 구간이 칸 4 ~ 5 면 mid = 4. 찾는 값이 더 커서 lo 를 옮겨야 할 때 lo 가 4 에 그대로 남아, 다음 걸음이 이번 걸음과 똑같습니다.
칸 4 칸 5 mid lo · hi lo = mid + 1 → 5
lo = mid + 1 (맞음). lo 가 5 로 옮겨 가 구간이 칸 5 하나로 줄어듭니다. 걸음마다 적어도 한 칸 줄어 끝에 닿습니다.

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 는 찾은 자리에 바로 넣어 줍니다.

어디에 쓰나

자주 묻는 것

정렬돼 있지 않으면 먼저 정렬하고 찾으면 되나요?

한 번만 찾을 거면 손해입니다. 정렬에는 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)

출처

← 힙과 우선순위 큐해시 테이블 →