이분 탐색 (Binary Search)

정의

이분 탐색 (Binary Search) 은 정렬된 시퀀스에서 목표값의 위치를 O(log N) 에 찾는 알고리즘. 매 단계에서 후보 구간을 절반으로 줄인다.

탐색이 본질이 아니어도, “답에 대해 단조성이 성립” 하기만 하면 답 자체를 이분 탐색 할 수 있다 (parametric search). 이 형태가 정렬 다음으로 PS 에서 가장 자주 등장한다.

문제 상황과 동기

길이 N 의 정렬된 배열에서 값 x 의 존재/위치를 알고 싶다.

• naive: 앞에서부터 선형 스캔. O(N).
• 이분 탐색: 매 단계에서 중간값과 비교, 후보 절반 버림. O(log N).

N = 10^9 일 때, naive 는 10초+ 걸리지만 이분 탐색은 약 30 단계로 끝난다. 단조성 (monotonicity) 만 있으면 검색·최적화 양쪽에 모두 적용 가능.

핵심 통찰: “x 가 후보 구간 어디에 있을 수 없다” 가 한 비교로 절반 결정.

시각화

핵심 아이디어

invariant: 답은 항상 [lo, hi] 구간 안에 있다. 매 단계에서 mid = (lo + hi) / 2 를 보고 비교.

초기: lo = 0, hi = N - 1
while lo <= hi:
    mid = (lo + hi) / 2
    if arr[mid] == x: 발견
    elif arr[mid] < x: lo = mid + 1  // 오른쪽 반쪽
    else:              hi = mid - 1  // 왼쪽 반쪽
없으면 -1 또는 삽입 위치

각 단계마다 구간 길이가 절반. 최대 ⌈log₂ N⌉ 단계.

알고리즘

표준 (값 찾기)

binary_search(arr, x):
    lo = 0, hi = N - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2     # 오버플로우 방지
        if arr[mid] == x:    return mid
        elif arr[mid] < x:   lo = mid + 1
        else:                hi = mid - 1
    return -1

lower_bound (x 이상의 첫 위치)

lower_bound(arr, x):
    lo = 0, hi = N
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if arr[mid] < x: lo = mid + 1
        else:            hi = mid
    return lo

hi = N 이 가능 (모든 원소가 x 보다 작은 경우). 표준 STL std::lower_bound 와 동작 동일.

parametric search (답에 이분 탐색)

f(k) = (k 가 답으로 가능한가) 가 단조 (false…false true…true) 이면, 가장 작은 k 를 이분 탐색.

parametric_search(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if f(mid):  hi = mid         # mid 가 가능 -> 답 후보
        else:       lo = mid + 1
    return lo                          # 가장 작은 가능 답

구현

// O(log N) 이분 탐색, lower_bound 변형
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  sort(a.begin(), a.end());
  int q; cin >> q;
  while (q--) {
      int x; cin >> x;
      int lo = 0, hi = n;
      while (lo < hi) {
          int mid = lo + (hi - lo) / 2;
          if (a[mid] < x) lo = mid + 1;
          else            hi = mid;
      }
      if (lo < n && a[lo] == x) cout << lo << "\n";
      else                        cout << -1 << "\n";
  }
}

# O(log N) 이분 탐색, bisect 모듈 사용
from bisect import bisect_left
import sys
input = sys.stdin.readline
​
n = int(input())
a = sorted(map(int, input().split()))
q = int(input())
out = []
for _ in range(q):
  x = int(input())
  i = bisect_left(a, x)
  out.append(str(i if i < n and a[i] == x else -1))
print("\n".join(out))

// O(log N) 이분 탐색, Arrays.binarySearch 또는 직접
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine().trim());
      int[] a = Arrays.stream(br.readLine().split(" "))
                      .mapToInt(Integer::parseInt).toArray();
      Arrays.sort(a);
      int q = Integer.parseInt(br.readLine().trim());
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          int x = Integer.parseInt(br.readLine().trim());
          int lo = 0, hi = n;
          while (lo < hi) {
              int mid = lo + (hi - lo) / 2;
              if (a[mid] < x) lo = mid + 1;
              else            hi = mid;
          }
          sb.append(lo < n && a[lo] == x ? lo : -1).append('\n');
      }
      System.out.print(sb);
  }
}

5
1 3 5 7 9
3
5
1
9

2
0
4

5
1 3 5 7 9
2
4
10

-1
-1

복잡도

변형 / 활용

함정

1. 정렬 가정

이분 탐색은 정렬된 입력 가정. 정렬되지 않은 입력에 적용하면 답이 틀린다 (혹은 0 회 매칭).

2. mid 계산 오버플로우

(lo + hi) / 2 는 lo, hi 가 큰 정수일 때 오버플로우 가능. lo + (hi - lo) / 2 가 안전 표준.

3. <= vs < 의 경계 처리

while (lo <= hi)   // 폐구간 [lo, hi], 종료 시 lo == hi + 1
while (lo < hi)    // 반열린 구간 [lo, hi), 종료 시 lo == hi

둘 다 맞지만 섞으면 무한 루프 / off-by-one. 한 가지 스타일을 일관되게.

4. 실수 이분 탐색

부동소수점 이분 탐색은 고정 횟수 (예: 100 회) 로 종료하는 것이 안전. lo < hi - 1e-9 같은 조건은 정밀도 문제.

for (int i = 0; i < 100; i++) {
    double mid = (lo + hi) / 2;
    if (f(mid)) hi = mid;
    else        lo = mid;
}

표준 라이브러리

BOJ 연습 문제

참고

• 매개 변수 탐색
• 삼분 탐색
• 정렬 알고리즘
• Aliens Trick (lambda 에 대한 이분 탐색)