이분 탐색

이분 탐색이란?

이분 탐색(binary search) 은 정렬된 데이터에서 찾는 값의 위치를 매번 후보
범위를 절반으로 줄여 가며 \(O(\log N)\)에 찾는 알고리즘입니다.

전화번호부에서 이름을 찾을 때 처음부터 한 장씩 넘기지 않고, 중간을 펼쳐 보고
앞/뒤를 결정하는 것과 똑같은 원리입니다.

전제 조건은 단 하나: 데이터가 정렬되어 있어야 합니다.

1. 동작 과정

찾는 값 target을 정렬된 배열에서 찾는 과정:

1. 범위의 가운데 mid를 본다.
2. a[mid] == target이면 찾았다.
3. a[mid] < target이면 답은 오른쪽 절반에 있다 → 왼쪽 버림.
4. a[mid] > target이면 답은 왼쪽 절반에 있다 → 오른쪽 버림.
5. 범위가 빌 때까지 반복.

매 단계마다 후보가 절반으로 줄어드니, \(N\)개를 단 \(\log_2 N\)번 만에 다 걸러냅니다.

2. 왜 \(O(\log N)\)인가

\(N\)을 절반으로 몇 번 나누면 1이 될까요? \(N \to N/2 \to N/4 \to \cdots \to 1\),
즉 \(\log_2 N\)번입니다. \(N = 10^9\)여도 약 \(30\)번이면 끝납니다.

이 압도적인 차이가 이분 탐색을 강력하게 만듭니다.

3. 단순 검색을 넘어서: 경계 찾기

이분 탐색의 진짜 위력은 "값이 있나?"가 아니라 "조건을 만족하는 경계" 를 찾는
데 있습니다.

• lower_bound: target 이상인 첫 위치.
• upper_bound: target 초과인 첫 위치.

이 둘만 있으면 "특정 값의 개수"(= upper - lower), "내 값 이상인 가장 작은 값"
등을 모두 구할 수 있습니다.

4. 결정 문제로의 일반화

배열이 아니어도 "답을 기준으로 조건이 한 번 거짓→참(또는 참→거짓)으로 바뀌는"
단조성이 있으면 이분 탐색을 쓸 수 있습니다. 이를 매개 변수 탐색
(parametric search) 이라 하며 별도 주제로 깊이 다룹니다.

예: "케이블을 길이 \(x\)로 자르면 \(K\)개 이상 나오는가?"는 \(x\)가 작을수록 참,
클수록 거짓입니다. 이 경계 \(x\)를 이분 탐색으로 찾습니다.

5. 정확성의 열쇠: 단조성

이분 탐색이 옳으려면 단조성(monotonicity) 이 반드시 있어야 합니다. 정렬된
배열에서는 "값이 커지는 순서"가 곧 단조성입니다. 결정 문제에서는 "조건의
참/거짓이 한 번만 바뀌는" 성질입니다. 이 성질이 없으면 절반을 버리는 것이
정당하지 않아 답이 틀립니다.

정리

이분 탐색은 정렬(또는 단조성)을 무기로 후보를 매번 절반씩 버려 \(O(\log N)\)에
답을 찾습니다. 단순 검색뿐 아니라 lower/upper_bound, 매개 변수 탐색으로 확장되는
강력한 도구입니다. 다음 강의에서 구현의 함정을 정복합니다.

이분 탐색을 정확히 짜기

이분 탐색은 원리는 쉽지만 off-by-one 실수가 잦기로 악명 높습니다. 정확한
구현 골격과 라이브러리 활용을 다룹니다.

1. 기본 검색 (값이 있는지)

bool found(vector<int>& a, int target) {
    int lo = 0, hi = a.size() - 1;
    while (lo <= hi) {                  // 닫힌 구간 [lo, hi]
        int mid = lo + (hi - lo) / 2;   // 오버플로 안전한 중간
        if (a[mid] == target) return true;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

(lo + hi) / 2는 두 수가 크면 오버플로할 수 있어 lo + (hi - lo) / 2로 씁니다.

2. lower_bound 직접 구현

target 이상인 첫 위치를 찾습니다. 반열린 구간 [lo, hi)로 짜는 것이 가장
실수가 적습니다.

int lowerBound(vector<int>& a, int target) {
    int lo = 0, hi = a.size();          // hi는 "끝 다음"
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;   // mid는 부족 → 버림
        else hi = mid;                       // mid가 후보 → 남김
    }
    return lo;                          // target 이상 첫 위치
}

upper_bound는 조건을 a[mid] <= target으로만 바꾸면 됩니다.

3. 라이브러리를 쓰자 (실전 권장)

직접 짜기보다 라이브러리가 안전합니다.

#include <algorithm>
sort(a.begin(), a.end());                       // 반드시 정렬!
auto lo = lower_bound(a.begin(), a.end(), x);    // x 이상 첫 위치
auto hi = upper_bound(a.begin(), a.end(), x);    // x 초과 첫 위치
int idx = lo - a.begin();                        // 인덱스로 변환
int count_x = hi - lo;                           // x의 개수
bool exists = (lo != a.end() && *lo == x);       // 존재 여부

import bisect
a.sort()                                  # 반드시 정렬!
lo = bisect.bisect_left(a, x)             # x 이상 첫 위치 (lower_bound)
hi = bisect.bisect_right(a, x)            # x 초과 첫 위치 (upper_bound)
count_x = hi - lo                         # x의 개수
exists = lo < len(a) and a[lo] == x

4. 답을 이분 탐색하기 (매개 변수 탐색 골격)

"가능한가?"가 단조이면 답 자체를 이분 탐색합니다.

// f(x) = x로 했을 때 가능하면 true (x가 클수록 어려워진다고 가정)
int lo = 0, hi = 1e9, ans = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (ok(mid)) { ans = mid; lo = mid + 1; }   // 되면 더 키워 본다
    else hi = mid - 1;
}
// ans = 가능한 최대 x

ok의 단조 방향(커지면 쉬워지나 어려워지나)에 따라 갱신 방향을 맞추는 것이
핵심입니다.

5. 흔한 실수

• 정렬 안 함 — 이분 탐색의 대전제. 정렬을 빼먹으면 답이 엉망.
• off-by-one — lo <= hi(닫힘)와 lo < hi(반열림)를 섞어 쓰면 무한 루프나
  경계 오류. 한 가지 스타일로 통일하세요.
• 무한 루프 — lo = mid(증가 안 함)로 쓰면 영원히 안 끝남. 검색은 mid + 1,
  경계 찾기는 반열림 구간으로.
• 오버플로 — (lo + hi) / 2 대신 lo + (hi - lo) / 2.
• lower vs upper 혼동 — "이상"은 lower, "초과"는 upper.

6. 패턴 알아보기

• "정렬된 데이터에서 찾기/세기" → lower/upper_bound.
• "\(N\)이 \(10^5\) 이상인데 \(O(N^2)\)가 필요해 보임" → 정렬 후 이분 탐색.
• "최대/최소 ~를 구하라 + 가능 여부 판정이 단조" → 답을 이분 탐색.

실전에서 이분 탐색 문제 알아보기

이분 탐색의 어려움은 구현이 아니라 "이게 이분 탐색 문제라는 사실을
알아채는 것" 입니다. 신호와 결정 절차를 정리합니다.

1. 출제 신호

• "최댓값의 최솟값", "최솟값의 최댓값" — 랜선 자르기, 공유기 설치류.
  이 문구는 사실상 매개변수 탐색하라는 지시문입니다.
• 답에 단조성이 있다 — "길이 \(x\)로 가능하면 \(x\)보다 짧은 길이도 가능"
  처럼, 가능/불가능이 한 지점에서 갈립니다.
• \(N\)이 매우 큰데 정답은 수치 하나 — \(N \le 10^{12}\) 같은 제한은 답의
  공간을 반씩 줄이라는 신호입니다.
• 정렬된 배열에서 위치/존재/개수 — lower_bound/upper_bound 직접 적용.
• "\(k\)번째로 작은 수"를 직접 나열할 수 없을 만큼 후보가 많은 경우.

2. 풀이 결정 절차

1. 무엇을 이분할지 정합니다 — 배열의 인덱스인가, 답 자체인가?
2. 답을 이분한다면 결정 함수 check(x) 를 정의합니다 — "\(x\)가 가능한가?"
   가 \(O(N)\) 정도로 판정되고, 결과가 단조인지 확인합니다.
3. 불변식을 정합니다 — 예: lo는 항상 가능, hi는 항상 불가능. 이 약속이
   초기값과 갱신식을 전부 결정합니다.
4. 답이 최대 가능인지 최소 가능인지에 따라 마지막에 lo/hi 중 무엇을
   출력할지 미리 적어 둡니다.

3. 자주 하는 실수

• 무한 루프. lo = mid로 줄이는 쪽이 있으면 mid는 올림으로 계산해야
  합니다. 불변식 기반의 다음 골격을 추천합니다.

// 불변식: 답은 [lo, hi] 안에 있고, check는 "x 이상이면 true"가 단조
long long lo = 1, hi = MAX_ANSWER;     // 닫힌 구간
while (lo < hi) {
    long long mid = lo + (hi - lo + 1) / 2;  // 올림! lo=mid가 있으므로
    if (check(mid)) lo = mid;                // mid 가능 → 더 키워 본다
    else            hi = mid - 1;            // 불가능 → 줄인다
}
cout << lo;                                  // lo == hi == 최대 가능값

• (lo + hi) / 2 오버플로. 둘 다 \(10^{18}\) 근처면 합이 넘칩니다.
  lo + (hi - lo) / 2로 쓰는 습관을 들이세요.
• check 안의 오버플로. "길이 \(x\)로 몇 개 나오나"의 합이 int를 넘는
  경우가 매우 흔합니다. 누적 변수는 long long으로.
• 경계 초기값. hi를 "가능한 최대 답"보다 작게 잡으면 정답이 구간 밖에
  있습니다. 0이나 최댓값 자체가 답이 되는 경우를 포함하는지 확인하세요.
• 실수 이분의 종료 조건. while (hi - lo > 1e-9)는 큰 수에서 영원히 안
  끝날 수 있습니다. 반복 횟수 고정(100회)이 안전합니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 정렬 배열
검색으로 몸을 풀고, "최댓값의 최솟값" 매개변수 탐색으로 넘어가세요.

문제마다 check 함수의 한 줄 정의와 단조성 방향을 먼저 주석으로 적은 뒤
골격을 채우면 off-by-one이 거의 사라집니다. 3문제 이상 풀어 클리어하면
레이팅의 CLASS 보너스에 반영됩니다.