이분 탐색

이분 탐색은 단조적인 비교·판정 결과를 이용해 후보 구간을 줄이며 경계를 찾는 알고리즘이다. 이 문서는 lower·upper bound, 중복과 범위 조회, 최소 용량과 정수 제곱근 응용, 정확성·종료 증명과 실제 대조 검사를 설명한다.

개요: 경계를 찾아 후보를 줄인다

이분 탐색(binary search), 또는 이진 탐색은 비교나 판정 결과를 이용해 후보 구간의 한쪽을 버리며 답을 찾는 방법이다. 정렬된 배열의 값 검색이 대표적이지만, 더 일반적으로는 거짓에서 참으로 한 번 바뀌는 판정의 경계를 찾는 데 사용할 수 있다.

핵심은 가운데를 고르는 문법이 아니라 버리는 구간에 답이 없다는 근거다. 정렬된 목록에서 가운데 값이 목표보다 작다면 그보다 왼쪽 값들도 작다는 성질을 이용한다. 이 성질이 없으면 절반을 버리는 선택이 답을 없앨 수 있다.

이 문서는 오름차순 배열에서 target 이상인 첫 위치를 찾는 반열린 구간 구현을 중심으로 설명한다. 존재 여부, 첫·마지막 위치, 삽입 위치와 범위 개수는 이 경계의 응용으로 연결한다. 서로 다른 구간 규칙의 코드를 부분적으로 섞지 않는 것이 중요하다.

Python 예제는 독립적으로 실행할 수 있도록 구성하되, 앞의 함수 정의를 함께 사용해야 하는 검증 예제는 별도로 표시한다. 일반 정수와 일관된 비교를 전제로 하며, 외부 입력의 자료형 검증과 동시 변경은 별도 계약으로 다룬다.

정렬과 단조성이라는 전제

오름차순 배열에서 “값이 target 이상인가”를 각 위치에 대해 계산하면 False가 이어지다가 True가 이어지는 형태가 된다. target이 모든 값보다 작으면 처음부터 모두 True이고, 모든 값보다 크면 끝까지 False다. 이 경계를 찾는 것이 lower bound다.

반드시 모든 문제에서 배열 전체가 정렬되어야만 하는 것은 아니다. 일반적인 경계 탐색에는 해당 판정에 대해 구간이 두 부분으로 나뉘는 성질이 필요하다. 다만 값 검색 API를 사용할 때는 그 API가 요구하는 정렬과 비교 규칙을 따라야 한다. “일부 입력에서 우연히 맞았다”는 것으로 전제를 생략하지 않는다.

아래 [2,4,4,9]와 target=4는 False,True,True,True가 된다. target=10이면 모두 False다. 반면 [4,2,9]에서는 True,False,True로 되돌아가므로 같은 경계 모델이 성립하지 않는다. 정렬 검사 자체는 선형 시간이 들 수 있으므로 반복 검색에서는 정렬을 언제 확인하고 어떻게 유지할지도 설계한다.

예제 코드

values = [2, 4, 4, 9]
print([value >= 4 for value in values])
print([value >= 10 for value in values])
print([value >= 4 for value in [4, 2, 9]])

실행 결과

[False, True, True, True]
[False, False, False, False]
[True, False, True]

반환값 계약: 원소 위치인가 경계인가

길이 n인 배열의 원소 인덱스는 0부터 n-1까지지만 삽입 경계는 0부터 n까지다. n은 마지막 원소 뒤라는 유효한 경계이며, 그 위치를 원소처럼 읽으면 범위를 벗어난다. 경계 함수의 결과를 바로 values[index]로 사용하지 않는 이유다.

찾는 값이 없을 때 None이나 -1을 반환하는 검색 함수와, 없더라도 정렬 순서를 유지하는 삽입 위치를 반환하는 함수는 다르다. 같은 binary search라는 이름을 가진 라이브러리라도 반환 계약이 다를 수 있으므로 언어를 옮길 때 확인해야 한다.

중복 값이 있을 때 임의의 일치 위치, 첫 일치 위치, 마지막 일치 위치도 서로 다른 계약이다. 목표와 같은 값을 만났다고 즉시 반환하면 보통 첫 위치를 보장하지 못한다. 첫 경계를 찾으려면 같은 값을 만난 경우에도 왼쪽을 더 살펴야 한다.

이 문서의 lower_bound는 target 이상인 첫 위치를 반환하고 없으면 n이다. upper_bound는 target보다 큰 첫 위치를 반환하고 없으면 n이다. 두 함수의 비교 연산 차이가 어떤 결과를 만드는지 이후 예제로 확인한다.

기본 구현: 반열린 구간 [lo, hi)

아래 함수는 lo=0, hi=n에서 시작한다. hi는 후보 원소를 직접 읽는 인덱스가 아니라 오른쪽 경계이므로 n으로 둘 수 있다. lo<hi인 동안 mid는 실제 배열 범위 안에 들어간다.

values[mid]가 target보다 작으면 mid까지의 원소는 답이 아니므로 lo=mid+1로 옮긴다. 그렇지 않으면 mid가 첫 경계일 수도 있으므로 hi=mid로 둔다. 같을 때 오른쪽을 버리고 왼쪽을 계속 살피는 것이 중복 중 첫 위치를 찾는 핵심이다.

[2,4,4,9]에서 target 4의 결과는 1, 5의 결과는 3, 10의 결과는 4다. 첫 번째는 실제 일치 위치이고 두 번째와 세 번째는 없는 값을 넣을 경계다. 빈 배열에서는 루프를 한 번도 돌지 않고 0을 반환한다.

예제 코드

def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
for target in [4, 5, 10]:
    print(lower_bound([2, 4, 4, 9], target))
print(lower_bound([], 4))

실행 결과

1
3
4
0

손으로 추적하기: 중복 값의 왼쪽 경계

입력이 [2,4,4,9]이고 target이 4라면 처음 구간은 [0,4), mid=2다. 값 4는 target보다 작지 않으므로 hi=2가 된다. 다음 [0,2)에서 mid=1의 값도 4이므로 hi=1이다. 마지막 [0,1)에서 mid=0의 값 2가 작으므로 lo=1이 된다.

이제 lo와 hi가 모두 1이므로 종료한다. 가운데에서 이미 4를 두 번 만났지만 즉시 반환하지 않았기 때문에 가장 왼쪽 경계를 찾았다. 같은 값이 많이 나오는 입력에서 임의 위치 검색과 경계 검색의 차이를 보여준다.

아래 추적 코드는 각 반복 시작의 lo,hi,mid와 비교 값을 기록한다. 출력의 세 줄이 위 설명과 일치한다. 디버깅할 때는 최종 답만 찍기보다 구간이 줄어드는지와 불변식이 유지되는지 확인하는 것이 도움이 된다.

예제 코드

values = [2, 4, 4, 9]
lo, hi = 0, len(values)
while lo < hi:
    mid = lo + (hi - lo) // 2
    print(lo, hi, mid, values[mid])
    if values[mid] < 4:
        lo = mid + 1
    else:
        hi = mid
print('answer', lo)

실행 결과

0 4 2 4
0 2 1 4
0 1 0 2
answer 1

정확성 증명: 버린 구간의 의미

lower_bound의 반복 불변식은 lo보다 왼쪽의 모든 값이 target보다 작고, hi 이상 위치의 모든 값이 target 이상이라는 것이다. 아직 결론 내리지 않은 구간은 [lo,hi)다. 초기에는 양쪽 버린 구간이 비어 있으므로 성립한다.

가운데 값이 작으면 정렬에 의해 그 왼쪽 값도 모두 작다. 따라서 mid까지 버리고 lo=mid+1로 옮겨도 불변식이 유지된다. 가운데 값이 작지 않으면 그 오른쪽 값도 target 이상이므로 hi=mid로 옮길 수 있다.

종료 시 lo==hi이므로 미확정 구간이 없다. 그 위치보다 왼쪽은 모두 작고 그 위치부터는 모두 target 이상이므로 정의한 첫 경계다. 결과가 n이면 모든 원소가 작다는 뜻이다.

이 설명은 비교 기준이 일관되고 검색 중 값이 변하지 않는다는 전제를 사용한다. 정렬되지 않은 자료나 매번 결과가 바뀌는 비교 함수를 넣으면 버린 구간에 대한 논리가 성립하지 않는다. 테스트와 별개로 전제와 불변식을 문서에 적어 두면 응용할 때 어떤 조건을 지켜야 하는지 알 수 있다.

종료 증명과 무한 반복의 흔한 원인

lo<hi일 때 mid는 lo 이상 hi 미만이다. hi=mid이면 오른쪽 경계가 엄격히 줄고, lo=mid+1이면 왼쪽 경계가 엄격히 늘어난다. 따라서 음이 아닌 구간 길이 hi-lo가 줄어 결국 0이 된다.

작은 값 분기에서 lo=mid로 쓰면 길이 1인 구간에서 mid==lo이므로 변화가 없다. 아래는 무한 반복을 실제로 실행하지 않고 한 번의 잘못된 갱신을 보여준다. [2]에서 3을 찾을 때 0,1이 그대로 남는다.

닫힌 구간 [lo,hi] 구현에서는 hi=mid-1과 while lo<=hi 같은 다른 조합을 사용할 수 있다. 그것도 올바르게 설계할 수 있지만 반열린 구간 코드와 일부 줄만 섞으면 답을 건너뛰거나 종료하지 않는 오류가 생긴다. 구간의 의미·조건·갱신·반환을 한 묶음으로 이해한다.

예제 코드

lo, hi = 0, 1
mid = (lo + hi) // 2
lo = mid
print(lo, hi)
lo = mid + 1
print(lo, hi)

실행 결과

0 1
1 1

존재 여부와 첫 일치 위치

경계를 얻은 뒤 index<n이고 values[index]==target인지 확인하면 존재 여부를 판별할 수 있다. 없다면 None을 반환하도록 래퍼를 만들 수 있다. 경계 계산과 결과 해석을 나누면 빈 배열과 모든 값보다 큰 target도 일관되게 처리된다.

아래는 Python 표준 라이브러리의 bisect_left를 사용한다. 4의 첫 위치는 1이고 5는 None이다. 만약 index<len(values) 검사를 빼면 10처럼 모든 값보다 큰 경우 IndexError가 발생할 수 있다.

동등성 비교와 정렬 비교가 서로 다른 의미를 사용하면 추가 검토가 필요하다. 대소문자를 무시한 키로 정렬했는데 원문 문자열의 정확한 일치를 찾는다면 경계에 같은 키를 가진 여러 항목이 있을 수 있다. 어떤 의미의 일치를 원하는지 명세해야 한다.

예제 코드

from bisect import bisect_left

def first_index(values, target):
    index = bisect_left(values, target)
    if index < len(values) and values[index] == target:
        return index
    return None

print(first_index([2, 4, 4, 9], 4))
print(first_index([2, 4, 4, 9], 5))
print(first_index([], 4))

실행 결과

1
None
None

upper bound와 같은 값의 개수

upper_bound는 target보다 큰 첫 위치다. lower_bound와 비교하면 작은 쪽으로 버리는 조건이 <에서 <=로 바뀐다. 같은 값을 만났을 때도 오른쪽으로 이동하므로 중복 구간의 끝을 찾는다.

[2,4,4,9]에서 4의 upper bound는 3이다. lower bound 1과의 차이 2가 4의 개수다. [lower,upper) 구간은 target과 같은 값들로 구성된다. 값이 없으면 두 경계가 같아서 개수는 0이다.

마지막 일치 위치는 upper-1이지만 먼저 개수가 0보다 큰지 확인해야 한다. upper가 0일 때 -1을 실제 인덱스로 쓰면 Python에서는 마지막 원소를 읽어 잘못된 결과가 나올 수 있다. 부재 표기와 음수 인덱스의 의미를 혼동하지 않는다.

예제 코드

def upper_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
from bisect import bisect_left
values = [2, 4, 4, 9]
left = bisect_left(values, 4)
right = upper_bound(values, 4)
print(left, right, right - left)
print(upper_bound(values, 5) - bisect_left(values, 5))

실행 결과

1 3 2
0

값 범위의 개수와 경계 선택

닫힌 값 범위 [a,b]에 들어가는 원소 수는 upper_bound(b)-lower_bound(a)로 구할 수 있다. 오른쪽 b를 포함하므로 b보다 큰 첫 위치를 사용한다. 반열린 값 범위 [a,b)라면 lower_bound(b)-lower_bound(a)다.

아래 [1,2,2,4,5,5,8]에서 2 이상 5 이하의 개수는 5이고, 2 이상 5 미만은 3이다. 구간 기호 하나가 실제 결과를 바꾸므로 API 설명에서 포함 여부를 명확히 표시한다. a>b인 역전 범위는 빈 결과로 볼지 오류로 볼지 별도 정책을 정한다.

경계 두 개를 찾는 비용은 O(log n)이지만 해당 원소를 모두 복사하거나 출력하면 결과 크기 k만큼 비용이 추가된다. 데이터베이스 범위 인덱스 조회에서도 경계를 찾는 일과 결과를 읽어 보내는 일을 분리해 생각하면 성능을 이해하기 쉽다.

예제 코드

from bisect import bisect_left, bisect_right
values = [1, 2, 2, 4, 5, 5, 8]
print(bisect_right(values, 5) - bisect_left(values, 2))
print(bisect_left(values, 5) - bisect_left(values, 2))

실행 결과

5
3

정렬된 삽입: 탐색 비용과 이동 비용

bisect는 정렬 순서를 유지할 삽입 위치를 찾을 수 있다. 같은 값보다 앞에 넣을지 뒤에 넣을지는 left와 right 경계로 선택한다. 그러나 Python 목록에 실제 삽입할 때 뒤 원소를 옮기는 비용이 발생하므로 전체 삽입은 일반적으로 선형 비용이 될 수 있다.

아래 [2,4,9]에 5를 삽입하면 [2,4,5,9]가 된다. 위치를 찾는 비교 횟수만 보고 “정렬된 목록 삽입은 O(log n)”이라고 쓰면 이동 비용을 빠뜨린다. 삽입이 많다면 균형 트리나 다른 정렬 컨테이너를 비교한다.

같은 키를 가진 레코드의 순서를 유지하려면 어떤 경계에 넣는지와 입력 순서를 함께 고려한다. 검색과 삽입 사이에 다른 코드가 목록을 바꾸면 구한 위치가 더 이상 맞지 않을 수 있다. 여러 실행 흐름의 변경을 허용하는 경우에는 두 단계의 일관성을 별도로 보장해야 한다.

예제 코드

from bisect import bisect_left
values = [2, 4, 9]
position = bisect_left(values, 5)
values.insert(position, 5)
print(position)
print(values)

실행 결과

2
[2, 4, 5, 9]

비교 키와 원본 위치

레코드를 날짜나 점수 같은 키로 정렬했다면 검색도 같은 키 기준을 사용한다. 키 배열을 따로 만들면 반복 검색에서 키 계산을 재사용할 수 있지만 원본 레코드와 키 배열의 순서가 계속 일치해야 한다.

아래는 점수 순서로 정렬한 레코드에서 80점 이상인 첫 위치를 찾는다. 키는 [65,80,80,95]이고 위치 1의 이름은 Ada다. 원래 입력 위치를 알아야 한다면 정렬 전에 인덱스를 함께 보관하는 등 추가 정보가 필요하다.

Python bisect의 key 매개변수는 지원 버전에서 원소의 비교 키를 계산하는 기능이지만 검색값 x에 같은 함수를 자동 적용하는지 등 세부 계약을 확인해야 한다. 이 문서는 버전 차이를 줄이기 위해 명시적인 키 배열을 사용하는 예제를 보여준다.

키를 만드는 비용이 비싸면 이진 탐색의 적은 비교 횟수보다 키 계산이 지배할 수 있다. 캐시된 키가 원본 수정 뒤 오래된 값이 되면 정렬 전제가 깨진다. 성능을 위해 중복 저장한 정보는 갱신 책임도 함께 가진다.

예제 코드

from bisect import bisect_left
rows = [('Lin', 65), ('Ada', 80), ('Sam', 80), ('Jo', 95)]
keys = [score for name, score in rows]
index = bisect_left(keys, 80)
print(index, rows[index][0])

실행 결과

1 Ada

일반화: 처음 참이 되는 정수 찾기

배열 대신 정수 x에 대한 단조 판정 predicate(x)를 사용할 수 있다. [lo,hi)에서 False가 이어지다가 True로 바뀐다면 처음 True인 x를 찾고, 없으면 원래 hi를 반환한다. hi 자체에는 판정을 호출하지 않는 계약이다.

아래 predicate(x)는 x≥7이고 검색 구간은 [0,10)이므로 결과는 7이다. 항상 False인 경우 10, 항상 True인 경우 0이다. 이 세 경우를 모두 처리하면 경계값의 의미가 분명해진다.

판정 함수가 비싸다면 전체 시간은 판정 한 번의 비용 C와 구간 폭 W에 대해 O(C log W) 형태가 된다. 단조성이 없는 판정, 외부 상태 때문에 호출마다 결과가 바뀌는 판정에는 적용할 수 없다. “답을 이분 탐색한다”는 표현 뒤에는 판정의 정의와 단조성 증명이 필요하다.

예제 코드

def first_true(lo, hi, predicate):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
print(first_true(0, 10, lambda x: x >= 7))
print(first_true(0, 10, lambda x: False))
print(first_true(0, 10, lambda x: True))

실행 결과

7
10
0

실전 응용: 정해진 기간에 운반할 최소 용량

양의 정수 무게를 가진 물건을 입력 순서대로 운반하고, 하루 용량을 넘지 않게 연속 구간으로 나눈다고 하자. 정해진 일수 안에 모두 운반할 수 있는 최소 용량을 구한다. 물건을 쪼개거나 순서를 바꾸는 문제와는 다르다.

용량 C로 가능하다면 더 큰 용량으로도 가능하므로 판정이 False에서 True로 바뀐다. 하한은 가장 무거운 물건이고 상한은 전체 무게 합이다. 상한에서는 하루에 모두 운반할 수 있어 적어도 하나의 가능한 답이 있음을 안다.

판정은 가능한 만큼 하루에 싣고 다음 물건이 넘으면 새 날을 시작한다. 순서를 유지하는 양의 무게 문제에서는 이렇게 채우는 것이 현재 용량에서 필요한 날 수를 최소화한다. 덜 싣고 일찍 끊는다고 이후 남은 물건을 더 적은 날에 처리할 수 있는 것은 아니기 때문이다.

[3,2,2,4,1,4]를 3일 안에 운반하는 최소 용량은 6이다. 용량 6에서는 [3,2], [2,4], [1,4]로 나눌 수 있다. 5에서는 이 순서를 유지하며 3일 안에 처리할 수 없다. 아래 결과는 6이다.

판정 한 번이 n개 물건을 순회하고, 용량 구간을 로그 단계로 줄이므로 일반 정수 연산 모델에서 O(n log S) 형태로 볼 수 있다. S는 탐색 범위와 관련된 총무게 규모다. 이 함수는 양의 정수 무게와 양의 정수 일수를 전제로 하며 자료형 전체를 검증하는 API가 아니다.

예제 코드

def minimum_capacity(weights, days):
    if not weights or days <= 0 or any(w <= 0 for w in weights):
        raise ValueError('positive weights and days required')
    def feasible(capacity):
        used_days = 1
        load = 0
        for weight in weights:
            if load + weight > capacity:
                used_days += 1
                load = 0
            load += weight
        return used_days <= days
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
print(minimum_capacity([3, 2, 2, 4, 1, 4], 3))
print(minimum_capacity([3, 2, 2, 4, 1, 4], 1))

실행 결과

6
16

판정 함수의 단조성을 증명하기

이분 탐색 응용에서 가장 먼저 확인할 것은 단조성이다. 운반 용량이 증가하면 기존의 운반 계획을 그대로 사용할 수 있으므로 가능한 상태가 불가능해지지 않는다. 이처럼 한 답의 증거를 더 큰 후보에서도 사용할 수 있는지 생각하면 단조성 근거를 찾기 쉽다.

반대로 “용량이 정확히 C인 상자를 모두 꽉 채울 수 있는가”는 다른 문제다. C가 커졌다고 정확히 맞출 수 있다는 보장은 없다. 비슷해 보이는 문장이라도 조건이 바뀌면 판정 형태가 True와 False 사이를 여러 번 오갈 수 있다.

최적화 문제를 결정 문제로 바꾸는 과정에서 요구사항을 바꾸지 않았는지도 확인한다. 최소 비용을 찾는데 판정이 일부 근사 전략의 성공 여부라면 원래 문제의 가능성과 같지 않을 수 있다. 잘못된 판정을 빠르게 탐색해도 올바른 최적해가 되지 않는다.

판정의 조기 종료는 결과를 바꾸지 않는 범위에서 사용할 수 있다. 필요한 날 수가 이미 제한을 넘었다면 남은 양의 무게를 처리해도 날 수가 줄지 않으므로 즉시 False를 반환할 수 있다. 이 역시 데이터 조건과 단조적인 상태 변화에 근거한다.

최대 가능한 값 찾기와 반대 방향

어떤 문제는 True가 이어지다가 False로 바뀌고 마지막 True를 찾는다. 이를 그대로 구현할 수도 있지만 False가 처음 되는 경계를 찾은 뒤 하나를 빼는 방식으로 바꿀 수 있다. 중요한 것은 항상 참이나 항상 거짓인 경우와 구간 밖 반환값을 정의하는 것이다.

아래 [0,11)에서 x²≤30인 마지막 정수는 5다. x²>30이 처음 참인 경계 6을 찾고 1을 뺀다. 실제 구현은 범위를 직접 줄이며 같은 의미를 확인한다. x가 음수가 포함된 구간이면 x²의 단조성이 달라지므로 이 예제의 비음수 조건이 필요하다.

마지막 참을 찾는 코드를 작성할 때 가운데를 내림할지 올림할지와 lo 갱신을 함께 검토한다. lo=mid를 사용하는 닫힌 후보 설계에서는 내림 mid 때문에 구간이 줄지 않는 경우가 생길 수 있다. 이미 검증한 첫 참 패턴으로 바꾸면 이런 혼동을 줄일 수 있다.

예제 코드

lo, hi = 0, 11
while lo < hi:
    mid = lo + (hi - lo) // 2
    if mid * mid > 30:
        hi = mid
    else:
        lo = mid + 1
print(lo - 1)

실행 결과

5

정수 제곱근: 부동소수점 없이 경계 찾기

음이 아닌 정수 n의 바닥 제곱근은 r²≤n<(r+1)²를 만족하는 r이다. 처음으로 x²>n이 되는 정수를 찾고 1을 빼면 된다. 실수 sqrt 결과를 정수로 바꾸는 방식과 달리 큰 정수에서도 정수 비교로 의미를 유지할 수 있다.

아래 0,1,15,16,17의 결과는 0,1,3,4,4다. 완전제곱수 바로 전과 같은 값, 바로 뒤를 검사하면 경계 처리 오류를 찾기 쉽다. Python의 정수는 큰 값을 표현할 수 있지만 큰 수 곱셈의 비용은 상수라고 볼 수 없으므로 비트 복잡도를 따로 고려할 수 있다.

고정 폭 정수 언어에서는 mid*mid가 넘칠 수 있다. 조건을 나눗셈 형태로 바꾸거나 더 넓은 타입과 안전한 연산을 사용하는 등 별도 처리가 필요하다. 나눗셈으로 바꿀 때도 mid=0을 처리해야 한다. 한 언어에서 실행한 코드를 다른 언어로 옮길 때 자료형 범위까지 검토한다.

실무 Python 코드에서 정수 제곱근이 필요하면 표준 math.isqrt를 우선 검토할 수 있다. 이 예제는 경계 탐색의 원리를 설명하기 위한 직접 구현이며 라이브러리의 구현 전략이나 성능과 동일하다고 주장하지 않는다.

예제 코드

def integer_sqrt(n):
    if n < 0:
        raise ValueError('nonnegative integer required')
    lo, hi = 0, n + 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mid * mid <= n:
            lo = mid + 1
        else:
            hi = mid
    return lo - 1
for n in [0, 1, 15, 16, 17]:
    print(n, integer_sqrt(n))

실행 결과

0 0
1 1
15 3
16 4
17 4

탐색 상한을 모를 때: 범위 확장

처음 참이 되는 값이 어딘지 모르지만 언젠가 존재한다고 보장된다면 상한을 1,2,4,8처럼 늘려 참인 지점을 찾은 뒤 그 구간에서 이분 탐색할 수 있다. 답의 크기를 A라고 할 때 범위 확장과 경계 탐색에 로그 단계의 판정이 필요하다.

아래 판정 x≥37에서 상한을 두 배씩 늘리면 64에서 참이 되고, 0부터 64까지 탐색해 37을 얻는다. 0에서 이미 참인지 먼저 확인하면 최소값 0도 처리할 수 있다.

참이 되는 값이 없을 수 있으면 무한히 확장해서는 안 된다. 최대 허용 범위, 횟수나 실패 반환을 정한다. 고정 폭 정수에서는 상한을 두 배로 만드는 연산도 오버플로할 수 있다. 판정 비용이 매우 크다면 범위 확장에 사용한 호출도 전체 성능에 포함한다.

실제 네트워크 서비스의 한계를 부하를 올리며 시험하는 것처럼 외부 상태를 바꾸는 판정은 순수 수학 함수와 다르다. 안전한 테스트 환경과 측정 설계 없이 이 패턴을 그대로 적용하지 않는다. 여기서는 부수 효과 없는 정수 판정을 사용한다.

예제 코드

def predicate(x):
    return x >= 37

hi = 1
while not predicate(hi):
    hi *= 2
lo = 0
while lo < hi:
    mid = (lo + hi) // 2
    if predicate(mid):
        hi = mid
    else:
        lo = mid + 1
print(lo)

실행 결과

37

정수 오버플로와 가운데 계산

(lo+hi)//2는 수학적으로 자연스럽지만 고정 폭 정수에서 lo+hi가 표현 범위를 넘을 수 있다. 비음수 인덱스 구간에서는 lo+(hi-lo)//2처럼 계산해 합의 범위를 줄이는 관용구를 사용한다. 사용 언어의 정수 규칙과 범위를 확인해야 한다.

이 대체식도 모든 부호 있는 범위에서 만능은 아니다. lo가 큰 음수이고 hi가 큰 양수이면 hi-lo 자체가 넘칠 수 있다. 인덱스가 비음수라는 조건과 임의의 정수 구간을 탐색하는 조건을 구분한다. 표준 라이브러리가 안전한 중간값 연산을 제공하는 환경도 있다.

오버플로 위험은 mid뿐 아니라 판정 함수 안의 합계와 곱셈에도 있다. 운반 용량의 sum(weights), 정수 제곱근의 mid*mid가 예다. 가운데 계산 한 줄만 바꾸고 전체 구현을 안전하다고 판단하면 안 된다.

Python 예제는 임의 정밀도 정수의 의미를 사용하므로 같은 종류의 고정 폭 넘침은 발생하지 않는다. 대신 값의 비트 수에 따른 비용이 증가한다. 언어별 차이를 명시하면 실행 예제의 보장 범위를 정확히 전달할 수 있다.

실수 구간의 이분법: 정수 탐색과 다른 종료

실수 구간에서는 mid+1로 이동하지 않는다. 연속 함수의 근을 찾는 수치 이분법은 부호가 다른 양 끝과 연속성 같은 조건을 사용하고, 구간 길이나 반복 횟수로 오차를 줄인다. 배열의 첫 경계 탐색과 관련된 아이디어지만 전제와 결과 보장은 다르다.

아래는 [1,2]에서 x²=2의 양의 해를 60회 구간 축소로 근사한다. 출력은 소수점 여섯 자리로 1.414214다. 반복 횟수를 고정해 실행이 종료되게 했으며 수치 표현의 반올림 때문에 무한히 정확해지는 것은 아니다.

while lo<hi만으로 실수 탐색을 끝내려 하면 mid가 반올림되어 lo나 hi와 같아진 뒤 구간이 더 줄지 않을 수 있다. 절대 오차와 상대 오차, 최대 반복 횟수를 정하고 필요하면 진전이 없는 상태를 감지한다.

함수값이 거의 0이라는 조건과 해의 위치 오차가 작다는 조건도 다르다. 함수의 기울기와 구간 특성에 따라 해석이 달라질 수 있다. 근이 없거나 여러 개인 경우, 불연속과 NaN 같은 입력을 어떻게 처리할지 명시한다.

예제 코드

lo, hi = 1.0, 2.0
for _ in range(60):
    mid = (lo + hi) / 2
    if mid * mid < 2:
        lo = mid
    else:
        hi = mid
print(f'{(lo + hi) / 2:.6f}')

실행 결과

1.414214

NaN과 비교의 일관성

부동소수점 NaN은 일반적인 대소 비교에서 특별한 동작을 한다. 아래 NaN<3, NaN≥3, NaN==NaN은 모두 False다. 따라서 모든 값이 작거나 크거나 같은 세 경우 중 하나라고 가정한 설명이 그대로 적용되지 않는다.

정렬과 검색에서 NaN을 허용한다면 언어 라이브러리가 정한 정렬 순서나 별도 키 규칙을 따라야 한다. 데이터 전처리에서 제외할지, 맨 앞이나 뒤로 보낼지, 누락값으로 별도 관리할지 결정한다. 임의의 비교 함수를 만들면서 일관된 순서 관계를 깨뜨리지 않도록 한다.

문자열 비교에서도 대소문자, 유니코드 정규화와 지역별 정렬 규칙에 따라 순서가 달라진다. 저장 시 사용한 키와 조회 시 사용한 키가 같아야 경계의 의미가 유지된다. “정렬되어 있다”는 말에는 어떤 비교 기준으로 정렬됐는지가 포함된다.

예제 코드

value = float('nan')
print(value < 3)
print(value >= 3)
print(value == value)

실행 결과

False
False
False

시간·공간 비용과 데이터 접근

후보 구간을 절반 정도로 줄이므로 판정 횟수는 구간 폭에 대해 O(log n)이다. 배열의 임의 접근과 비교가 상수 시간일 때 전체 탐색 시간도 로그 수준으로 설명할 수 있다. 반복 구현은 경계와 가운데 같은 고정 수의 변수를 사용한다.

비교가 긴 문자열이나 복잡한 레코드 계산이라면 비교 비용을 곱해야 한다. 연결 리스트에서 중간 위치까지 이동하거나 순차 이터레이터를 진행하는 경우에는 비교 횟수와 실제 이동 횟수가 다르다. C++ 표준의 관련 알고리즘도 반복자 종류에 따른 이 차이를 구분한다.

재귀 구현이 배열 슬라이스를 만들어 넘기면 로그 깊이와 별개로 복사 비용이 생긴다. 원래 배열과 인덱스 범위를 넘기는 방식은 이런 비용을 줄일 수 있다. 구현 형태를 보지 않고 알고리즘 이름만으로 시간과 공간을 결정하지 않는다.

반복 질의에서는 정렬이나 키 배열 구축 비용을 나눠 감수할 수 있다. 단 한 번의 검색을 위해 매번 정렬한다면 선형 탐색보다 전체 작업이 비쌀 수 있다. 자료의 갱신과 삽입 비용도 함께 비교해야 한다.

언어별 표준 API의 반환 계약

Python의 bisect_left와 bisect_right는 삽입 경계를 반환한다. Java Arrays.binarySearch는 일치한 인덱스를 반환하거나 없을 때 삽입 위치를 음수 형태로 인코딩한 값을 반환한다. Rust 슬라이스의 binary_search는 성공 위치와 삽입 위치를 Result의 서로 다른 경우로 구분한다.

이들 일반 검색 API에서 중복 값의 첫 위치가 자동으로 보장된다고 가정하지 않는다. 첫·마지막 경계가 필요하면 해당 언어의 경계 검색 기능이나 명시적인 구현을 사용한다. 반환 형식이 다르므로 -1만 검사하는 습관을 다른 언어에 그대로 옮기면 잘못된 처리가 될 수 있다.

Go의 sort.Search는 길이 n의 인덱스 구간에서 판정이 처음 참이 되는 위치를 찾는 인터페이스를 제공한다. C++에는 lower_bound, upper_bound, equal_range처럼 경계와 범위를 구하는 기능이 있다. 실제 사용 시 버전별 문서와 비교 조건을 확인한다.

이 절은 공식 API 계약을 비교한 설명이며 Java·Rust·Go·C++ 코드를 모두 실행한 검증은 아니다. 이 문서의 실행 결과와 대조 테스트는 Python 예제를 대상으로 한다. 특정 언어의 예제를 추가할 때는 그 환경에서 별도로 컴파일·실행해 확인해야 한다.

동시 변경과 결과 인덱스의 수명

이분 탐색은 탐색하는 동안 정렬과 판정 결과가 안정적이라는 가정을 사용한다. 다른 실행 흐름이 원소를 삽입하거나 키 값을 바꾸면 이전 비교로 버린 구간의 의미가 달라질 수 있다. 검색과 삽입을 연속 호출한다고 두 동작이 하나의 원자적 작업이 되는 것은 아니다.

반환된 인덱스 역시 목록 변경 뒤에는 다른 원소를 가리킬 수 있다. 장기간 보관할 식별자가 필요하면 위치 번호보다 안정적인 ID를 사용하거나 버전과 함께 다룬다. 스냅샷 복사, 잠금, 불변 자료나 읽기 전용 버전 등 선택에는 시간·메모리 비용이 있다.

판정 함수가 현재 시각이나 외부 서비스의 변하는 상태를 읽으면 같은 x에 대해 다른 결과를 낼 수 있다. 이 경우 단순한 first_true 증명의 전제가 성립하지 않는다. 측정 잡음이 있는 최적화 문제는 별도의 통계적 방법과 재시도 정책을 요구할 수 있다.

표준 라이브러리 문서의 스레드 안전성 범위를 확인한다. 개별 읽기 연산이 안전하다는 말과 검색 전체에서 정렬된 스냅샷을 본다는 보장은 다르다. 자료 구조와 동기화 정책을 함께 설계한다.

테스트 설계: 예시 몇 개보다 작은 영역 전수 검사

경계 탐색은 빈 배열과 중복, 구간 양 끝에서 오류가 자주 발생한다. 작은 값 영역의 모든 정렬 배열을 생성하고 결과를 표준 라이브러리와 대조하면 이런 실수를 찾기 쉽다. 아래 코드는 앞의 lower_bound와 upper_bound 정의 뒤에 붙여 실행한다.

값 0,1,2,3으로 만들 수 있는 길이 0부터 6까지의 비감소 배열을 모두 생성한다. target은 -1부터 4까지 검사한다. 배열 210개마다 6개 target을 사용하고 두 경계를 비교하므로 총 2520개 결과를 확인한다.

추가로 반환 위치 왼쪽은 모두 작고 오른쪽은 모두 크거나 같다는 성질을 검사할 수도 있다. 정수 제곱근은 r²≤n<(r+1)²라는 조건을, 최소 용량은 반환값에서 가능하고 바로 아래에서는 불가능하다는 조건을 확인한다. 답을 계산하는 다른 구현과 불변식 검사를 함께 사용하면 근거가 더 강해진다.

전수 검사는 선택한 유한 영역에 한정된다. 큰 값의 오버플로, 비싼 비교, 동시 변경 같은 문제를 자동으로 검증하지 않는다. 테스트 결과와 정확성 증명, 환경별 제한을 구분해 기록한다.

예제 코드

from itertools import combinations_with_replacement
from bisect import bisect_left, bisect_right
checks = 0
for length in range(7):
    for values in combinations_with_replacement(range(4), length):
        for target in range(-1, 5):
            assert lower_bound(values, target) == bisect_left(values, target)
            assert upper_bound(values, target) == bisect_right(values, target)
            checks += 2
print(checks)

실행 결과

2520

응용 검증: 정수 제곱근과 최소 용량

아래 검사는 앞의 integer_sqrt와 minimum_capacity 정의 뒤에 붙여 실행한다. 정수 제곱근은 0부터 1000까지 표준 math.isqrt와 비교한다. 최소 용량은 길이 1부터 4, 무게 1부터 3으로 만들 수 있는 모든 목록과 가능한 일수에 대해 연속 구간 분할을 완전 탐색한 결과와 대조한다.

기준 구현은 모든 절단 위치 조합을 만들고, 각 구간의 합 중 최댓값이 최소가 되는 분할을 고른다. 효율적인 방법은 아니지만 작은 입력에서 정답 판정기로 쓰기 좋다. 이분 탐색의 판정 함수와 다른 방식으로 답을 구하므로 같은 실수를 반복할 가능성을 줄인다.

출력은 제곱근 1001개와 용량 426개 검사다. 실제 대형 입력의 속도를 측정한 결과가 아니라 작은 영역에서 정확성을 확인한 결과다. 구현을 바꿀 때 이런 검사를 다시 실행하면 경계 처리와 판정 로직의 회귀를 발견할 수 있다.

예제 코드

from math import isqrt
from itertools import product, combinations
for n in range(1001):
    assert integer_sqrt(n) == isqrt(n)
capacity_checks = 0
for length in range(1, 5):
    for weights in product(range(1, 4), repeat=length):
        for days in range(1, length + 1):
            best = sum(weights)
            for cuts in combinations(range(1, length), days - 1):
                boundaries = (0,) + cuts + (length,)
                largest = max(sum(weights[boundaries[i]:boundaries[i + 1]]) for i in range(days))
                best = min(best, largest)
            assert minimum_capacity(weights, days) == best
            capacity_checks += 1
print(1001, capacity_checks)

실행 결과

1001 426

문제에 적용하는 순서

먼저 찾는 것이 값 하나인지 경계인지, 최소 가능한 값인지 최대 가능한 값인지 정한다. 판정을 문장으로 쓰고 True와 False가 어떤 순서로 나타나는지 증명한다. 다음으로 탐색 범위와 답이 없는 경우, 양 끝이 포함되는지를 정의한다.

구현에서는 구간 규칙 하나를 일관되게 사용한다. 가운데 계산, 비교 조건, 경계 갱신과 반환값을 함께 검토하고 매 반복에서 구간이 반드시 줄어드는지 확인한다. 정수 범위와 판정 내부의 넘침, 실수의 반올림과 종료 정책도 점검한다.

작은 입력을 손으로 추적하고, 빈 입력·중복·모든 참·모든 거짓을 테스트한다. 표준 함수나 선형 탐색, 완전 탐색 같은 독립적인 기준 해법과 대조한다. 빠른 검색이라는 이유로 전처리와 실제 결과 출력 비용을 빼지 않는다.

이분 탐색을 익히는 핵심은 짧은 코드를 암기하는 것이 아니라 어떤 후보를 왜 버릴 수 있는지 설명하는 데 있다. 그 근거가 명확하면 배열 검색에서 용량 최적화와 정수 경계 문제까지 같은 원리를 안전하게 확장할 수 있다.

참고 자료