이분 탐색

🎯 학습 목표

이 강을 마치면 이분 탐색을 오류 없이 구현할 수 있습니다. 특히 경계 처리— left <= right인지 left < right인지, mid를 어디로 옮길지 — 를 근거를 갖고 정할 수 있게 됩니다.

그리고 이분 탐색의 진짜 힘인 "답의 범위를 이분 탐색하는" 응용, 이른바 파라메트릭 서치를 익힙니다. 코딩 테스트에서 이분 탐색 문제의 상당수가 이 형태입니다.

💡 절반씩 버리기

이분 탐색(binary search)은 정렬된 데이터에서 값을 찾는 방법입니다. 가운데를 보고 찾는 값이 왼쪽에 있는지 오른쪽에 있는지 판단해 절반을 통째로 버립니다.

[1, 3, 5, 7, 9, 11, 13] 에서 11 찾기

  단계 1
   1   3   5   7   9  11  13
   ↑           ↑           ↑
  left        mid        right
   mid 값 7 < 11  → 왼쪽 절반은 볼 필요 없다
   left = mid + 1

  단계 2
                   9  11  13
                   ↑   ↑   ↑
                 left mid right
   mid 값 11 == 11 → 찾았다

  ▲ 7개를 2번 만에 찾았다
    100만 개여도 약 20번이면 끝난다 (2강)

  ▲ 전제 조건 : 반드시 정렬돼 있어야 한다
    정렬 안 된 배열에 쓰면 잘못된 답이 나온다.
    (오류가 안 나고 조용히 틀리므로 더 위험하다)

  비용 비교
   순차 탐색 O(n)      : 100만 개 → 최악 100만 번
   이분 탐색 O(log n)  : 100만 개 → 약 20번

   ※ 단, 정렬이 안 돼 있다면 정렬 비용 O(n log n)이 붙는다.
     한 번만 찾을 거면 그냥 순차 탐색이 낫다.
     여러 번 찾을 거면 정렬해 두고 이분 탐색이 이득이다.

📖 경계 처리 — 이분 탐색이 어려운 진짜 이유

원리는 쉬운데 구현에서 무한 루프나 오답이 나는 경우가 많습니다. 원인은 거의 항상 경계 조건입니다. 두 가지 형태를 구분해 외워 두는 것이 안전합니다.

형태 A — 값이 정확히 있는지 찾기

  left, right = 0, len(arr) - 1     ← right 가 '마지막 인덱스'
  while left <= right:              ← 등호 있음
      mid = (left + right) // 2
      if arr[mid] == target: return mid
      elif arr[mid] < target: left = mid + 1
      else: right = mid - 1
  return -1

  ▲ 핵심
   · right 가 유효한 인덱스이므로 left == right 도 검사해야 한다
     → while 에 등호가 필요
   · mid 를 이미 확인했으므로 mid ± 1 로 건너뛴다
     → 이래야 구간이 반드시 줄어들어 무한 루프가 안 난다

형태 B — 조건을 만족하는 '경계'를 찾기

  left, right = 0, len(arr)         ← right 가 '길이' (인덱스 밖)
  while left < right:               ← 등호 없음
      mid = (left + right) // 2
      if 조건(arr[mid]):
          right = mid               ← mid 를 버리지 않는다
      else:
          left = mid + 1
  return left                        ← left == right 가 답

  ▲ 핵심
   · 답이 될 수 있는 후보를 남겨야 하므로 right = mid
   · 그래서 while 에 등호를 쓰면 무한 루프가 난다
   · 끝나면 left 와 right 가 같아지고 그 자리가 경계다

  ▲ 무한 루프가 나는 전형적 조합
    while left <= right  +  right = mid   ← 구간이 안 줄어든다

형태 B가 바로 "조건을 만족하는 첫 위치"를 찾는 틀입니다. 정확히 같은 값이 없어도 "이 값 이상이 처음 나오는 자리"를 찾을 수 있어 활용도가 훨씬 높습니다.

파이썬에는 이 기능이 표준 라이브러리로 들어 있습니다. bisect 모듈입니다.

함수	하는 일	복잡도
bisect_left(a, x)	x를 넣을 수 있는 가장 왼쪽 위치	O(log n)
bisect_right(a, x)	x를 넣을 수 있는 가장 오른쪽 위치	O(log n)
insort(a, x)	정렬을 유지하며 삽입	O(n) ← 삽입이 O(n)

bisect_right(a, x) - bisect_left(a, x)로 x의 개수를 O(log n)에 셀 수 있습니다. 자주 쓰는 기법입니다.

💻 실전 예제 — 직접 구현과 파라메트릭 서치

from bisect import bisect_left, bisect_right


def binary_search(arr, target):
    """값의 인덱스를 찾는다. 없으면 -1 → O(log n)"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1           # 오른쪽 절반만 남긴다
        else:
            right = mid - 1          # 왼쪽 절반만 남긴다
    return -1


def min_capacity(weights, days):
    """weights 를 days 일 안에 순서대로 옮길 때 필요한 최소 하루 용량"""
    def can_do(cap):
        need, current = 1, 0
        for w in weights:
            if current + w > cap:    # 오늘은 더 못 싣는다
                need += 1            # 다음 날로
                current = 0
            current += w
        return need <= days

    left, right = max(weights), sum(weights)   # 답이 있을 범위
    while left < right:                        # 형태 B
        mid = (left + right) // 2
        if can_do(mid):
            right = mid              # 이 용량으로 되니 더 줄여 본다
        else:
            left = mid + 1           # 안 되니 늘려야 한다
    return left


nums = [1, 3, 3, 3, 7, 9]
print(binary_search(nums, 7))              # 4
print(binary_search(nums, 4))              # -1
print(bisect_left(nums, 3), bisect_right(nums, 3))   # 1 4
print(bisect_right(nums, 3) - bisect_left(nums, 3))  # 3 (3의 개수)
print(min_capacity([1, 2, 3, 4, 5], 3))    # 6

코드를 줄 단위로 보겠습니다.

• mid = (left + right) // 2 — 파이썬은 정수 크기 제한이 없어 오버플로 걱정이 없습니다. C++·자바에서는 left + (right - left) // 2를 쓰는 관례가 있습니다.
• left = mid + 1 / right = mid - 1 — mid는 이미 확인했으므로 건너뜁니다. 이것이 형태 A의 원칙입니다.
• def can_do(cap) — 파라메트릭 서치의 핵심입니다. "용량이 cap이면 가능한가?"라는 예·아니오 질문으로 바꿉니다.
• if current + w > cap — 오늘 더 실으면 용량을 넘으므로 날짜를 하루 넘깁니다. 그리디하게 최대한 채우는 방식입니다.
• left, right = max(weights), sum(weights) — 답의 범위를 잡습니다. 가장 무거운 물건은 하루에 실어야 하므로 최소는 max, 전부 하루에 실으면 sum이 최대입니다.
• if can_do(mid): right = mid — 가능하면 답이 될 수 있으므로 버리지 않고 범위만 줄입니다. 형태 B입니다.
• 복잡도는 O(n log(sum))입니다. 이분 탐색이 log(sum)번 돌고, 매번 can_do가 O(n)입니다.

파라메트릭 서치는 "최솟값의 최대" 또는 "최댓값의 최소"를 구하라는 문제에서 씁니다. 그 조건이 단조적일 때 — 즉 "cap이 되면 cap+1도 된다"가 성립할 때 — 만 쓸 수 있습니다.

⚠️ 자주 하는 실수

첫째, 정렬을 안 하고 이분 탐색합니다. 오류가 안 나고 조용히 틀린 답이 나오므로 가장 위험합니다. 이분 탐색을 쓰기 전에 정렬 여부를 반드시 확인하세요.

둘째, 무한 루프를 만듭니다. while left <= right와 right = mid를 섞어 쓰면 구간이 줄지 않아 멈추지 않습니다. 형태 A와 B를 통째로 외워 두고 섞지 마세요.

셋째, insort가 O(log n)인 줄 압니다. 위치를 찾는 것은 O(log n)이지만 삽입 자체가 O(n)입니다(3강). 반복문 안에서 쓰면 O(n²)가 됩니다.

넷째, 답의 범위를 너무 좁게 잡습니다. 파라메트릭 서치에서 right를 실제 답보다 작게 잡으면 영영 찾지 못합니다. 범위는 넉넉하게 잡아도 log이라 비용이 거의 안 늘어납니다.

다섯째, 단조성을 확인하지 않습니다. "조건을 만족하는 구간이 연속적인가"를 따져야 합니다. 조건이 참·거짓을 오가면 이분 탐색을 쓸 수 없습니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	이분 탐색은 정렬된 데이터에서 O(log n)
2	형태 A: left <= right + mid ± 1
3	형태 B: left < right + right = mid
4	두 형태를 섞으면 무한 루프
5	bisect로 경계·개수를 O(log n)에
6	파라메트릭 서치 — 답의 범위를 이분 탐색
7	쓸 수 있는 조건은 단조성

지금 해 볼 것은 형태 A의 right = mid - 1을 right = mid로 바꿔 실행해 보는 것입니다. 무한 루프가 나는 것을 직접 보면 왜 두 형태를 섞으면 안 되는지 확실히 각인됩니다.

다음 11강 「투 포인터」에서는 정렬된 배열을 다루는 또 다른 기법을 봅니다. 4강 회문 판별에서 잠깐 썼던 양 끝에서 좁혀 오는 방식을 일반화해, O(n²) 이중 반복문을 O(n)으로 바꾸는 패턴을 익히겠습니다.

📚 참고 자료

• bisect — Array bisection algorithm — Python 공식 문서
• list.sort() — Python 공식 문서
• TimeComplexity — Python Wiki