이진 탐색

이진 탐색은 정렬해 둔 값 가운데서 찾는 값이 어디 있는지 짚어 내는 방법입니다. 가운데 값 하나와 견주어 답이 없는 쪽 절반을 통째로 버립니다. 이 일을 되풀이하면 값이 백만 개여도 스무 번 남짓 견주고 끝납니다.

상세

종이 사전에서 낱말을 찾는 일과 닮았습니다. 첫 장부터 넘기지 않고 가운데쯤을 펼쳐 봅니다. 찾는 낱말이 펼친 쪽보다 뒤에 있으면 앞쪽 절반은 다시 펴 볼 일이 없습니다.

이름의 「이진」은 남은 범위를 매번 둘로 가른다는 뜻입니다. 둘로 갈라 한쪽만 남기는 일을 답이 나올 때까지 되풀이합니다.

넣는 것은 오름차순으로 정렬된 값 목록과 찾는 값 하나입니다. 나오는 것은 그 값이 목록에서 몇 번째에 있는지, 곧 위치입니다. 목록에 없으면 없다는 답이 나옵니다. 정렬해 둔 사원 번호 목록에서 사원 번호 하나가 몇 번째에 있는지 찾는 일이 그런 경우입니다.

절반씩 버리는 절차

값 열 개가 오름차순으로 놓여 있다고 하겠습니다. 2 · 5 · 8 · 12 · 16 · 23 · 38 · 56 · 72 · 91 에서 23 을 찾습니다. 아래 표는 견줌 세 번으로 끝나는 과정입니다.

아래 그림은 같은 과정을 칸으로 늘어놓은 것입니다. 층마다 남아 있는 칸과 이번에 버리는 칸이 몇 개인지를 보입니다.

flowchart TD
    subgraph W1["견줌 1 · 남은 칸 열 개"]
        a1["2"]
        a2["5"]
        a3["8"]
        a4["12"]
        a5["16 ← 가운데"]
        a6["23"]
        a7["38"]
        a8["56"]
        a9["72"]
        a10["91"]
    end
    subgraph W2["견줌 2 · 남은 칸 다섯 개"]
        b1["23"]
        b2["38"]
        b3["56 ← 가운데"]
        b4["72"]
        b5["91"]
    end
    subgraph W3["견줌 3 · 남은 칸 두 개"]
        c1["23 ← 가운데"]
        c2["38"]
    end
    W1 -->|"23 이 더 크다 · 왼쪽 다섯 칸을 버린다"| W2
    W2 -->|"23 이 더 작다 · 오른쪽 세 칸을 버린다"| W3

남은 개수가 열에서 다섯, 둘로 줄었습니다. 개수가 짝수면 가운데가 둘입니다. 어느 쪽을 골라도 됩니다. 위 표는 왼쪽을 골랐습니다.

표의 세 줄을 일반화하면 아래 갈림이 됩니다.

flowchart TD
    A["찾을 범위 · 처음에는 전체"] --> B{"범위가 비었나"}
    B -->|"비었다"| C["없다고 답한다"]
    B -->|"남았다"| D["가운데 값과 견준다"]
    D -->|"같다"| E["몇 번째인지 답한다"]
    D -->|"찾는 값이 더 크다"| F["왼쪽 절반을 버린다"]
    D -->|"찾는 값이 더 작다"| G["오른쪽 절반을 버린다"]
    F --> B
    G --> B

절반을 버린 뒤에는 남은 쪽을 새 범위로 삼아 같은 갈림으로 돌아옵니다. 한 바퀴마다 범위가 반으로 줄어드니 몇 바퀴 만에 끝납니다.

견줌 횟수

값이 n 개일 때 최악의 견줌 횟수는 n 을 1 이 될 때까지 반으로 나눈 횟수입니다. 반으로 나누기를 몇 번 했는지 세는 것을 log 라고 합니다.

값 백만 개를 반으로 나누어 가면 스무 단 만에 하나로 줄어듭니다.

flowchart TD
    N1["1,000,000"] --> N2["500,000"]
    N2 --> N3["250,000"]
    N3 --> N4["125,000"]
    N4 -->|"같은 나누기를 열일곱 번 더"| N5["1"]

이 횟수를 빅오 표기법으로 O(log n) 이라고 적습니다. 빅오 표기법은 값의 개수가 늘어날 때 비용이 어떤 모양으로 따라 늘어나는지를 적는 약속입니다.

값이 두 배로 늘어도 나누기가 한 번만 더 붙습니다. 그래서 값이 많아질수록 이진 탐색과 순차 탐색의 차이가 벌어집니다. 순차 탐색은 앞에서부터 하나씩 견주는 방법입니다.

아래 표는 값의 개수를 천 배씩 늘리며 두 방법의 견줌 횟수를 견준 것입니다.

값이 십억 개면 한쪽은 십억 번을 견주고 다른 쪽은 서른 번을 견줍니다.

최악일 때와 보통일 때가 크게 다르지 않습니다. 둘 다 O(log n) 입니다. 운이 좋아 첫 가운데 값이 곧바로 답이면 한 번에 끝납니다.

쓰는 메모리는 값의 개수와 상관없이 일정합니다. 범위의 양 끝 위치를 담는 수 두 개면 됩니다. 목록을 따로 복사하지 않습니다.

이진 탐색이 전제하는 세 가지

첫째, 값이 정렬돼 있어야 합니다. 정렬돼 있지 않으면 절반을 버리는 판단 자체가 틀립니다. 버린 쪽에 답이 들어 있을 수 있기 때문입니다.

둘째, 가운데 값을 한 번에 꺼낼 수 있어야 합니다. 배열은 몇 번째인지만 알면 그 값으로 바로 갑니다. 연결 리스트는 앞 칸에서 다음 칸으로 따라가야 해서 가운데를 꺼내는 데만 개수에 비례하는 시간이 듭니다.

flowchart TD
    subgraph 배열["배열 · 화살표 한 번"]
        A1["첫째"]
        A2["둘째"]
        A3["셋째 ← 가운데"]
        A4["넷째"]
        A5["다섯째"]
    end
    subgraph 연결리스트["연결 리스트 · 화살표 셋"]
        B1["첫째"] --> B2["둘째"]
        B2 --> B3["셋째 ← 가운데"]
        B3 --> B4["넷째"]
        B4 --> B5["다섯째"]
    end
    Q1["가운데를 달라"] --> A3
    Q2["가운데를 달라"] --> B1

화살표 개수가 그대로 비용입니다. 연결 리스트에서는 가운데를 꺼낼 때마다 이 따라가기가 붙으므로 절반씩 버려도 이득이 사라집니다.

셋째, 정렬해 두는 비용을 이진 탐색이 갚아야 합니다. 같은 목록을 여러 번 찾을 때라야 그 비용이 값을 합니다.

한 번 찾으려고 정렬 알고리즘부터 돌리면 손해입니다. 정렬은 목록을 한 번 훑는 것보다 언제나 비쌉니다. 한 번 훑는 비용은 O(n) 입니다. 정렬은 대개 O(n log n) 입니다. n 에 반으로 나누기 횟수를 곱한 값이라 언제나 더 큽니다.

구현할 때 자주 나는 오류

양 끝의 위치를 더해 둘로 나누면 가운데 위치가 나옵니다. 그런데 정수가 담을 수 있는 크기가 정해진 언어에서는 두 위치의 합이 그 크기를 넘을 수 있습니다. 넘치면 값이 음수로 바뀌어 엉뚱한 데를 봅니다.

아래에서 low 는 범위의 왼쪽 끝 위치, high 는 오른쪽 끝 위치, mid 는 구하려는 가운데 위치입니다.

mid = (low + high) / 2         // 넘친다
mid = low + (high - low) / 2   // 안전하다

아랫줄은 두 위치의 차를 먼저 구한 뒤 왼쪽 끝에 더합니다. 차는 목록 길이보다 작으니 넘칠 일이 없습니다.

범위를 줄일 때는 방금 견준 가운데 값까지 같이 버려야 합니다. 그 값을 범위에 남겨 두면 범위가 줄지 않고 같은 값을 영영 견줍니다.

같은 값이 여럿 들어 있으면 그중 아무거나 하나를 짚습니다. 첫 번째나 마지막 위치가 필요하면 견줌 규칙을 바꾼 하한 탐색과 상한 탐색을 씁니다.

찾는 값이 목록에 없으면 범위가 빈 채로 끝납니다. 이때 남아 있는 왼쪽 끝 위치가 그 값을 끼워 넣을 곳입니다. 앞의 열 칸에서 20 을 찾으면 아래처럼 끝납니다.

flowchart TD
    subgraph 끝난상태["20 을 찾다가 범위가 빈 상태"]
        d1["2"]
        d2["5"]
        d3["8"]
        d4["12"]
        d5["16"]
        d6["23"]
        d7["38"]
        d8["56"]
        d9["72"]
        d10["91"]
    end
    H["high · 오른쪽 끝"] --> d5
    L["low · 왼쪽 끝"] --> d6
    H -.->|"둘이 엇갈리면 끝난다"| L

low 가 high 보다 오른쪽으로 넘어가면서 끝났습니다. 20 은 16 과 23 사이에 들어가야 합니다. low 가 가리키는 곳이 바로 그 23 입니다. 순서를 지키며 새 값을 넣을 때 이 성질을 그대로 씁니다.

쓸 때와 안 쓸 때

정렬된 상태가 오래 유지되고 찾는 일이 잦으면 잘 맞습니다. 목록을 한 번 정렬해 두고 조회만 되풀이하는 경우입니다.

값이 자주 바뀌어 순서를 계속 지켜야 하면 비용이 그쪽으로 옮겨 갑니다. 키가 정확히 일치하는 것만 찾으면 해시테이블이 더 낫습니다. 키를 위치로 바꾸는 계산을 한 번 하면 견줄 것도 없이 바로 그 위치로 가기 때문입니다.

대신 해시테이블은 순서를 안 지킵니다. 「10 이상 20 이하」처럼 범위로 묻는 질문에는 답하지 못합니다. 이진 탐색은 범위가 시작되는 위치를 바로 짚어 주므로 그런 질문에 맞습니다.

값이 몇 개 안 되면 하나씩 훑는 쪽이 코드도 짧고 대개 충분합니다.

저장 구조 안의 이진 탐색

정렬된 목록 위에서 도는 절차라 저장 구조 안쪽에 자주 박혀 있습니다.

SSTable처럼 키를 정렬해 담은 파일은 메모리에 올려 둔 인덱스에서 읽을 블록 하나를 이진 탐색으로 고릅니다. 일관성 해싱은 원 위에 흩어 둔 점들을 정렬해 두고 키 다음에 오는 점을 찾습니다.

B-tree는 노드 하나에 키 여러 개를 정렬해 담습니다. 그 안에서 내려갈 가지를 같은 방식으로 고릅니다.

flowchart TD
    R["루트 노드 · 10 · 20 · 30"]
    R -->|"10 미만"| K1["가지 1"]
    R -->|"10 이상 20 미만"| K2["가지 2"]
    R -->|"20 이상 30 미만"| K3["가지 3"]
    R -->|"30 이상"| K4["가지 4"]

노드 안에서 키 셋을 견주어 가지 하나를 고르는 것이 이진 탐색 한 번입니다. 고른 가지로 한 층 내려가면 거기서 또 한 번 같은 일을 합니다.

찾는 대상이 값일 필요는 없습니다. 「어느 지점부터 조건이 참이 되나」가 정해져 있으면 같은 절반 버리기를 쓸 수 있습니다. 어느 커밋부터 버그가 생겼는지 찾는 git bisect가 그렇게 돕니다. 커밋을 시간 순으로 놓으면 어느 지점부터는 계속 「버그 있음」이기 때문입니다.

관련 항목

이진 탐색이 속하는 상위 분류

알고리즘 · 탐색 알고리즘 · 분할 정복 · 자료구조

이진 탐색이 도는 자료구조

배열 · 정렬된 배열 · 인덱스 · B-tree · SSTable · 이진 탐색 트리 · 균형 이진 탐색 트리 · 스킵 리스트 · LSM 트리

같은 찾기 문제를 푸는 다른 방법

순차 탐색 · 해시테이블 · 보간 탐색 · 지수 탐색 · 점프 탐색 · 트라이 · 블룸 필터

이진 탐색이 전제하는 성질

정렬 · 전순서 · 단조성 · 임의 접근 · 불변 조건

이진 탐색 앞에 치르는 정렬 비용

정렬 알고리즘 · 퀵소트 · 병합 정렬 · 힙소트 · 삽입 정렬

견줌 횟수를 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 로그 함수

이진 탐색을 구현할 때 나는 오류

정수 오버플로 · 오프바이원 · 무한 루프 · 경계 조건

견줌 규칙을 바꾸거나 다른 대상에 적용한 갈래

하한 탐색 · 상한 탐색 · 파라메트릭 서치 · 삼분 탐색 · git bisect