동작 원리

이 장에서는 작은 배열로 이진 탐색이 실제로 어떻게 구간을 줄여 가는지 한 단계씩 따라가 봅니다. 값 찾기, lower_bound·upper_bound, 답을 이분 탐색하는 경우, 삼분 탐색까지 같은 방식으로 추적합니다. 핵심은 "답은 항상 현재 구간 안에 있다"는 불변식이 매 단계 지켜진다는 점입니다.

값 찾기 추적

정렬된 배열 a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91](인덱스 0~9)에서 23을 찾습니다. 닫힌 구간 [lo, hi]를 쓰고 mid = (lo + hi) // 2입니다.

원소 10개를 3번 비교로 끝냈습니다. 없는 값 24를 찾으면 4단계째에 lo = 6, hi = 5가 되어 구간이 비고, 반복이 끝나며 -1을 돌려줍니다. 구간이 비었다는 것이 "없다"는 증거입니다.

lower_bound 추적

중복이 있는 a = [1, 2, 2, 2, 3, 5]에서 lower_bound(2), 즉 a[i] >= 2인 첫 인덱스를 구합니다. 반열린 구간 [lo, hi)로 시작해 lo = 0, hi = 6입니다. 규칙은 하나뿐입니다. a[mid] < x이면 답은 mid보다 오른쪽이므로 lo = mid + 1, 아니면 mid가 답일 수도 있으므로 hi = mid.

upper_bound(2)는 비교만 a[mid] <= x로 바꾸면 됩니다. 같은 배열에서 mid = 3(값 2, 이동 lo = 4), mid = 5(값 5, hi = 5), mid = 4(값 3, hi = 4)를 거쳐 4를 돌려줍니다. 따라서 2의 개수는 4 - 1 = 3입니다.

아래 코드는 이 추적표를 직접 출력합니다. 다른 배열과 값으로 바꿔 가며 손으로 그린 표와 맞춰 보면 경계 처리가 빠르게 몸에 익습니다.

def lower_bound_trace(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        go_right = a[mid] < x
        print(f"lo={lo} hi={hi} mid={mid} a[mid]={a[mid]} -> {'lo' if go_right else 'hi'}")
        if go_right:
            lo = mid + 1
        else:
            hi = mid
    return lo


print(lower_bound_trace([1, 2, 2, 2, 3, 5], 2))   # 1

왜 끝나고, 왜 맞는가

반열린 구간 꼴에서는 lo < hi인 동안 lo <= mid < hi가 성립합니다. lo = mid + 1이나 hi = mid 어느 쪽이든 구간 길이가 적어도 1 줄어들므로 반복은 반드시 끝납니다. 또 "인덱스 lo 앞은 모두 x보다 작고, 인덱스 hi부터는 모두 x 이상"이라는 불변식이 유지되므로, lo == hi가 되는 순간 그 자리가 바로 경계입니다.

흔한 실수는 lo = mid로 쓰는 것입니다. lo + 1 == hi일 때 mid가 lo와 같아져 구간이 줄지 않고 무한 반복에 빠집니다. 닫힌 구간과 반열린 구간을 섞어 쓰는 것도 한 칸 어긋남(off-by-one) 오류의 주된 원인이므로, 한 가지 꼴을 정해 일관되게 쓰는 것이 좋습니다.

답을 이분 탐색하기: 정수 제곱근

n = 40의 정수 제곱근, 즉 r * r <= n인 가장 큰 r을 구해 봅니다. 조건 P(r) = r * r > n은 r이 커지면서 거짓에서 참으로 한 번만 바뀝니다. 처음 참이 되는 r을 찾고 1을 빼면 답입니다.

def first_true(lo, hi, pred):
    # [lo, hi)에서 pred가 F..F T..T 꼴일 때 첫 T의 위치(없으면 hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def isqrt(n):
    return first_true(0, n + 2, lambda r: r * r > n) - 1


print(isqrt(40), isqrt(0), isqrt(1), isqrt(49))   # 6 0 1 7

n = 40일 때 mid는 21, 10, 5, 8, 7, 6 순서로 바뀌고 구간 [7, 7)에서 멈춰 7을 돌려줍니다. 따라서 답은 6입니다. 검사 범위 위쪽을 n + 2로 잡은 이유는 (n + 1) ** 2 > n이 항상 참이어서 첫 참이 반드시 범위 안에 들기 때문입니다.

삼분 탐색

단봉 함수 f의 최댓값 위치를 실수 구간 [lo, hi]에서 찾을 때는 두 점 m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3을 비교합니다. f(m1) < f(m2)이면 최댓값은 m1보다 오른쪽에 있으므로 lo = m1, 아니면 hi = m2입니다. 매번 구간이 3분의 2로 줄어듭니다.

def ternary_max(f, lo, hi, iterations=100):
    for _ in range(iterations):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1
        else:
            hi = m2
    return (lo + hi) / 2


print(round(ternary_max(lambda x: -(x - 2) ** 2 + 5, 0, 10), 6))   # 2.0

정수 범위라면 f(m) < f(m + 1)을 조건으로 쓰는 이진 탐색이 더 간단하고 비교 횟수도 적습니다. 다만 값이 같은 평평한 구간이 있으면 두 방법 모두 단조성이 깨져 올바르게 동작하지 않을 수 있습니다.

정리

• 이진 탐색은 매 단계 구간을 절반으로 줄이며, 구간이 비거나 lo와 hi가 만나면 끝납니다.
• 반열린 구간 [lo, hi)에서 lo = mid + 1과 hi = mid만 쓰면 무한 반복과 off-by-one을 피하기 쉽습니다.
• 단조 조건의 첫 참을 찾는 first_true 하나로 lower_bound, 정수 제곱근, 최적화 문제를 모두 풀 수 있습니다.
• 삼분 탐색은 단봉 함수의 극값을 찾으며, 정수에서는 이웃 비교 이진 탐색으로 바꿔 쓸 수 있습니다.