Binary Search

정의

결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법

구현 방법

1. [lo, hi]가 check(lo) != check(hi)가 되도록 구간 설정
2. while(lo+1 < hi)동안 mid = (lo+hi)/2에서 check(mid) = check(lo)라면 lo = mid, 아니라면 hi = mid
3. 구한 경계에서 답이 lo인지 hi인지 생각해본 후 출력

문제 2805번: 나무 자르기

#include <bits/stdc++.h>
#define MAX 1000000
using namespace std;

int n, m, v[MAX];

// 결정 문제
bool check(const int mid) { // mid 높이에 절단기를 위치했을 때 m 이상의 나무를 얻을 수 있는가?
    long long sum = 0; // 오버플로우 조심
    for (int i = 0; i < n; i++) {
        if (v[i] > mid) sum += v[i] - mid;
    }
    return sum >= m;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> v[i];

    // 이분 탐색
    int lo = 0, hi = MAX;
    // Checklist
    // 1. Check(lo) = T, Check(hi) = F를 만족?
    // 2. lo는 정답이 될 수 있는 모든 범위를 나타낼 수 o? (정답은 0 ~ max(v) - 1라 가능)

    while (lo + 1 < hi) { // lo와 hi 사이에 다른 칸이 존재하는가?
        int mid = (lo + hi) / 2; // 항상 lo < mid < hi를 만족 (평균을 생각해보면 o)
        if (check(mid)) lo = mid;
        else hi = mid;
    }
    cout << lo << '\n'; // T~F의 분포이므로 lo가 정답
}