이진 탐색 — 정렬된 배열에서 O(log n)

정렬된 배열에서 특정 값을 찾는다고 하자. 앞에서부터 하나씩 비교하면 최악의 경우 원소를 전부 봐야 하니 O(n)이다. 하지만 배열이 정렬돼 있다는 사실을 쓰면 훨씬 빠르게 찾을 수 있다. 이게 이진 탐색이다.

절반씩 지운다

한가운데 값을 본다. 찾는 값이 그보다 크면 왼쪽 절반은 통째로 버리고, 작으면 오른쪽 절반을 버린다. 한 번 비교할 때마다 남은 후보가 절반으로 줄어든다. n개에서 시작해 절반씩 줄이면 1이 될 때까지 약 log₂ n번이면 끝나므로 O(log n)이다. 원소가 백만 개여도 스무 번 남짓이다.

핵심 전제는 하나다. 배열이 정렬돼 있어야 한다. 정렬돼 있지 않으면 “가운데보다 크니 왼쪽은 볼 필요 없다”는 판단 자체가 성립하지 않는다.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid          # 찾음: 인덱스 반환
        elif arr[mid] < target:
            lo = mid + 1        # 오른쪽 절반만 남긴다
        else:
            hi = mid - 1        # 왼쪽 절반만 남긴다
    return -1                    # 없음

자주 틀리는 세 곳

이진 탐색은 개념은 쉬운데 손으로 짜면 미묘하게 틀리기로 악명 높다. 걸리는 곳은 대개 정해져 있다.

경계 조건. while lo <= hi인가 lo < hi인가, hi를 len(arr)로 둘지 len(arr) - 1로 둘지에 따라 갱신식(mid + 1, mid - 1, mid)이 달라진다. 위 코드는 “[lo, hi] 양끝 포함 구간”으로 잡았으므로 종료 조건이 lo <= hi이고, 후보에서 뺀 칸은 mid ± 1로 확실히 건너뛴다. 한 가지 규약을 정하고 끝까지 그걸 지키는 게 요령이다.

무한 루프. 구간이 줄지 않으면 영영 끝나지 않는다. lo = mid처럼 갱신하면 lo와 hi가 붙었을 때 mid가 다시 lo가 되어 제자리를 맴돌 수 있다. 위처럼 mid + 1/mid - 1로 반드시 한 칸 이상 좁히면 안전하다.

중간값 오버플로. (lo + hi) // 2는 Python에선 정수 범위가 무제한이라 괜찮지만, C·Java처럼 정수에 상한이 있는 언어에선 lo + hi가 자료형을 넘칠 수 있다. 그래서 lo + (hi - lo) // 2로 쓰는 습관이 안전하다. 결과는 같지만 큰 값을 더하지 않는다.

값이 없을 때 — lower/upper bound

실전에선 “그 값이 있냐”보다 “그 값이 들어갈 자리가 어디냐”가 더 자주 필요하다. 중복이 있을 때 첫 위치, 마지막 위치, 삽입 지점 같은 것들이다. 이걸 lower bound(≥ target인 첫 위치)와 upper bound(> target인 첫 위치)라고 부른다.

def lower_bound(arr, target):
    lo, hi = 0, len(arr)        # hi를 len(arr)로 (반열린 구간)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # target 이상이면 이 지점도 후보로 남긴다
    return lo                    # target이 없으면 삽입 위치를 가리킨다

upper_bound는 조건을 arr[mid] <= target으로 바꾸면 된다. 둘의 차이(upper - lower)가 곧 배열 속 target의 개수다. Python이라면 표준 라이브러리 bisect의 bisect_left/bisect_right가 정확히 이 둘이라 직접 짤 일은 많지 않지만, 원리를 알아야 응용이 된다.

매개변수 탐색 — 답을 직접 못 셀 때

이진 탐색의 진짜 힘은 배열 검색을 넘어선다. “최댓값을 구하라” 같은 최적화 문제를, “값이 x일 때 조건을 만족하나?”라는 예/아니오 판정 문제로 바꿀 수 있을 때, 그 답 후보 범위를 이진 탐색으로 좁힌다. 이걸 매개변수 탐색(parametric search)이라 부른다.

성립 조건은 단조성이다. x에서 조건이 참이면 그보다 쉬운 쪽에서도 참이어야 한다. 그래야 “여기서 참이면 더 볼 필요 없다”가 성립해 절반을 버릴 수 있다.

예를 들어 “길이 L인 랜선들을 잘라 n개를 만들 때 가능한 최대 조각 길이”를 구한다고 하자. 조각 길이를 정하면 몇 개 나오는지는 쉽게 셀 수 있고, 길이가 짧을수록 개수는 늘어난다(단조). 그러니 길이를 이진 탐색한다.

def max_piece_length(lines, n):
    lo, hi = 1, max(lines)
    answer = 0
    while lo <= hi:
        mid = lo + (hi - lo) // 2               # 후보 길이
        count = sum(line // mid for line in lines)
        if count >= n:                           # 이 길이로 n개 이상 나온다
            answer = mid                         # 성공 기록 후 더 길게 시도
            lo = mid + 1
        else:
            hi = mid - 1                         # 너무 길다, 줄인다
    return answer

정렬된 배열이 없어도, 후보 답의 범위만 있으면 이진 탐색이 걸린다. 문제에서 “최대·최소를 구하라”가 나오고 답을 하나 정했을 때 가부 판정이 쉽다면, 매개변수 탐색을 떠올려 볼 만하다. O(log n)의 절반 버리기가 검색을 넘어 최적화까지 닿는 지점이다.