이분탐색

탐색 범위를 줄여가며 탐색하는 방법.

mid 값을 정해서 범위를 줄여나간다.

숫자 정해두고 맞추는 업다운게임과 비슷한 방법.

 

시간 복잡도는 연산 한 번으로 범위를 절반으로 줄이기 때문에 Log N

 

이분탐색 코드는 두 부분으로 나뉜다.

 

1. 범위를 줄여나가는 부분 -> 이분 탐색
2. 범위를 줄일 기준을 정하는 부분(ask 함수 : T/F 반환) -> 결정 문제

 

1번 부분에서는 left, right, mid값을 정해서

2번 부분이 리턴하는 값에 따라 left, right의 값을 조절해 범위를 줄여나간다.

 

예시로 백준의 나무 자르기 문제(https://www.acmicpc.net/problem/2805)를 풀어보면,

 

1번 부분 코드 (이분 탐색)

while (left < right) {
        mid = (left + right) / 2;
        if (ask(mid)) {
            answer = mid;
            left = mid + 1;
        } else right = mid;
    }

2번 부분 코드 (결정 문제)

bool ask(int cutH) {
    gain = 0;
    for (int i = 0; i < n; i++) {
        if(tree[i]<=cutH) break;
        gain += tree[i]-cutH;
    }
    bool result = gain >= m;
    return result;
}

 

트리 배열을 돌면서 cutH 값을 기준으로 잘라내면 가져갈 수 있는 나무의 길이(gain)를 얻게 된다.

gain 값이 집에 가져가고자 하는 길이(M)보다 크거나 같다면 true를 리턴한다.

그리고 이 말은 자르는 기준(cutH)이 더 높아도 된다는 의미이므로 left를 줄여서 범위를 재조정한다.

만약 gain 값이 M보다 작다면 기준이 너무 높은 것이므로 right를 줄인다.

이 과정을 반복하다가 left가 right와 만나는 순간에 정답이 left에 남아있게 된다.