이진 탐색 (Binary Search)

"업다운 게임"을 코드로 옮긴 것. 정렬된 데이터에서 가운데를 확인하고, 답이 왼쪽인지 오른쪽인지 판단해 탐색 범위를 절반씩 버린다. 100만 개에서 20번, 10억 개에서 30번이면 끝난다.

1. 업다운 게임으로 이해하기

1~100 중 하나를 정해 두고 친구가 맞힌다. "50?" → "업(더 큼)" → "75?" → "다운(더 작음)" → "62?" … 이렇게 매번 남은 후보의 절반을 지운다. 최악이라도 7번(⌈log₂100⌉)이면 반드시 맞힌다.

2. 배열에서 한 단계씩 실행해 보기

lo(왼쪽 끝)와 hi(오른쪽 끝)로 살아있는 범위를 표시한다. 매 단계 mid = (lo + hi) // 2 를 확인하고:

• arr[mid] == target → 찾음, 끝
• arr[mid] < target → 정답은 오른쪽 → lo = mid + 1 (왼쪽 절반 폐기)
• arr[mid] > target → 정답은 왼쪽 → hi = mid - 1 (오른쪽 절반 폐기)
• lo > hi 가 되면 → 배열에 없음

3. 왜 O(log n) 인가

n개에서 시작해 매 비교마다 후보가 n → n/2 → n/4 → … 로 줄어든다. 후보가 1개 이하가 될 때까지 걸리는 횟수 k는:

아래 그래프는 n이 커질 때 두 방식의 비교 횟수 차이를 보여준다. 선형은 직선으로 치솟고, 이진 탐색은 거의 눕는다.

4. 코드 — 반복문 버전

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1          # 양 끝(닫힌 구간 [lo, hi])
    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                             # 배열에 없음

5. 변형 — "같은 값" 말고 "경계" 찾기

실무에서 더 자주 쓰는 건 정확히 일치하는 값이 아니라 삽입 위치 / 첫 번째 위치 / 마지막 위치다. Python bisect, C++ lower_bound가 이걸 한다.

"정답에 대한 이진 탐색" (parametric search)

배열이 아니라 답 자체를 이진 탐색하기도 한다. "조건을 만족하는 최소값 k"를 찾을 때, k가 커질수록 조건이 거짓→참으로 한 번만 바뀐다면(단조성), 그 경계를 log 번의 판정으로 찾는다.

# 예: 나무를 잘라 M미터 이상 얻는 절단기 높이의 최댓값
lo, hi = 0, max(trees)
while lo < hi:
    mid = (lo + hi + 1) // 2
    if total_cut(trees, mid) >= M:   # 높이 mid로 충분한가?
        lo = mid                     # 더 높여 보자
    else:
        hi = mid - 1
return lo

6. 어디에 쓰이나