이진 탐색
정렬된 배열에서 가운데를 보고 값이 있을 수 없는 절반을 버리며 값을 찾습니다. 비교할 때마다 남은 부분이 절반으로 줄어듭니다.
- 최선 Ω(1)
- 평균 Θ(log n)
- 최악 O(log n)
- 메모리 O(1)
용어 설명
- 정렬됨: 오름차순으로 놓인 상태. 이진 탐색에는 이것이 필요하며, 정렬되지 않은 데이터에서는 틀린 답을 냅니다.
- 절반으로 나누기: 비교할 때마다 목표가 있을 수 없는 쪽 절반을 버리는 것.
- log₂ n: 1이 남을 때까지 n을 몇 번 절반으로 나눌 수 있는지. 64개면 6번이므로 비교는 최대 7번입니다.
- 가운데 (mid)
- 찾음
- 제외됨
- 목표
탐색이 고를 수 있는 모든 가운데 값. 한 번의 실행은 아래로 내려가는 하나의 길입니다. 단계: 5 = ⌈log₂(24 + 1)⌉, 필요할 수 있는 최대 비교 횟수.
정렬된 값 24개 가운데서 70를 찾습니다. 아직 배열 전체가 후보입니다.
스페이스바: 재생 또는 일시정지. 좌우 화살표 키: 단계 이동. Home과 End 키: 처음과 끝으로 이동.
해 보세요: 배열에 없는 목표를 고르세요. 그래도 탐색은 lo가 hi를 넘는 순간, 최대 ⌈log₂(n + 1)⌉번의 비교로 끝납니다.
작동 방식
이진 탐색은 목표가 아직 있을 수 있는 구간 양쪽에 lo와 hi라는 두 표시를 둡니다. 가운데 값을 보고, 그것이 목표면 끝입니다. 더 작으면 목표는 오른쪽에만 있으므로 lo를 가운데 뒤로, 더 크면 hi를 가운데 앞으로 옮깁니다. 한 단계마다 남은 부분이 절반이 되므로 64개는 최대 7번, 백만 개도 최대 20번이면 됩니다. lo가 hi를 넘으면 남은 것이 없으니 값은 배열에 없습니다.
언제 쓰면 좋을까
데이터가 정렬되어 있고 어느 위치로든 바로 갈 수 있을 때 쓰세요. 정렬된 목록의 단어, 릴리스 기록의 버전, git bisect, 정렬된 배열의 삽입 위치 등입니다. 정렬되지 않은 데이터에서는 틀린 답을 내며, 먼저 정렬하는 것은 여러 번 찾을 때만 이득입니다.