이진 탐색: 답이 있는 구간을 매번 절반으로 줄이기
이진 탐색은 비교 결과에 따라 후보 구간의 절반을 버리는 방법이다. 정렬 배열 검색으로 알려져 있지만 본질은 조건이 한 방향으로만 변하는 단조성이다. 조건이 false인 구간 뒤에 true인 구간이 이어지면 최초 true 위치를 찾을 수 있다.
비교 결과에 따라 정답이 있을 수 있는 구간만 남긴다.
구간의 뜻을 고정한다
아래 lower_bound는 정렬된 배열에서 target 이상인 첫 위치를 반환한다. 탐색 범위를 반열린 구간 [left,right)로 정하고, 답이 배열 끝일 수도 있어 초기 right를 n으로 둔다.
def lower_bound(sorted_values, target):
left = 0
right = len(sorted_values)
while left < right:
middle = left + (right - left) // 2
if sorted_values[middle] < target:
left = middle + 1
else:
right = middle
return left
def contains(sorted_values, target):
position = lower_bound(sorted_values, target)
return position < len(sorted_values) and sorted_values[position] == target
left보다 앞의 값은 target보다 작다고 이미 확인했고, right 이상은 답의 후보 경계 바깥이다. middle 값이 작으면 middle까지 제외해 left=middle+1, 크거나 같으면 middle 자체가 답일 수 있어 right=middle로 둔다. 이 불변식이 경계 처리를 설명한다.
중복과 없는 값도 처리하기
[1,3,3,7,9]에서 target=3이면 최초 위치 1을 얻는다. target=6이면 위치 3이 나오지만 값은 7이므로 실제 존재하지 않는다. target=10이면 n이 반환된다. 위치를 얻은 뒤 배열에 접근하기 전에 범위를 검사해야 한다.
각 단계에서 후보 길이가 대략 절반이 되어 비교 횟수는 O(log n), 반복 구현의 추가 공간은 O(1)이다. n개 데이터를 먼저 정렬해야 한다면 그 비용을 따로 더해야 하며 한 번의 조회만 한다면 선형 탐색보다 유리하지 않을 수도 있다.
폐구간 [left,right] 구현도 가능하지만 종료 조건과 갱신 규칙이 달라진다. 서로 다른 방식의 right 초기값, while 조건, middle 이동을 섞으면 무한 반복이나 한 칸 오류가 생긴다. 코드를 외우기보다 어느 위치가 아직 답일 수 있는지 말로 설명하는 것이 좋다.
고정 폭 정수에서는 (left+right)//2가 오버플로할 수 있어 left+(right-left)//2를 쓴다. Python 정수에는 같은 문제가 없지만 알고리즘을 다른 언어로 옮길 때 의미가 있다.
최소 용량, 최소 시간처럼 답 자체에 이진 탐색을 적용할 수도 있다. 이 경우 “용량 x에서 가능하다면 더 큰 용량에서도 가능하다” 같은 단조 조건을 먼저 증명해야 한다. 판정 함수가 O(f(n))이면 전체 비용은 탐색 단계 수에 그 판정 비용을 곱한 값이다. 단조성이 없으면 절반을 버리는 근거도 없다.