이분탐색 | NORANG

며칠동안 이분 탐색 문제를 풀면서 이분 탐색 잘 짜는 법을 정리해봤다.
다음과 같은 조건을 만족하는 이분탐색 문제가 있다고 하자.

vector에서 s, e 사이에 주어진 limit에 대하여 check()를 만족시키는 최대 정수값을 찾는다.
vector 안의 값은 정렬되어 있다.
vector 안에 반드시 check()를 만족시키는 값이 존재한다.

int binary_search(vector<int> &v, int limit, int s, int e) {
    // base case
    if (e - s <= 1) {
        if (check(v, e, limit)) return e;
        else return s;
    }
    int mid = (s+e)/2;

    // minimize solution's range
    if (check(v, mid, limit)) return binary_search(v, mid, e);
    else return binary_search(v, s, mid-1);
}

가장 유의해야 하는 부분은 아래와 같이 두 부분으로 나눌 수 있다.

minimize solution’s range

이분 탐색의 핵심은 해가 존재하는 범위를 줄여나가는 것이다.
주어진 해의 범위 [s, e]에서 그 중간값 mid가 조건을 만족할 경우와 만족하지 않는 경우로 구분하여 재탐색한다.

만족하는 경우

문제는 주어진 범위에서 최대값을 찾는 것이다.
mid는 우선 답이 될 수 있으며 mid보다 크고 e이하인 모든 값은 정답이 될 수 있다.
따라서 [mid, e]의 범위에서 다시 탐색해야 한다.

문제가 조건을 만족하는 최소값 탐색인 경우, 반대로 [s, mid]를 탐색하면 될 것이다.

만족하지 않는 경우

mid가 조건을 만족하지 않으므로 mid는 해의 범위에서 제외된다.
그러므로 이 값보다 더 작은 것이 우리가 구하는 최대값일 것이다.
따라서 [s, mid-1]의 범위에서 다시 탐색한다.

최소값 탐색의 경우 [mid+1, e]를 탐색하면 될 것이다.

base case

반드시 해가 존재하는 이분 탐색에서 가장 중요한 것은 정지 조건이다.
해가 존재하므로, 예외값을 따로 처리할 필요는 없다.
다만 구간의 크기가 1 또는 2일 경우가 문제된다.

구간의 크기가 1

가령 [1, 1]의 경우, mid = 1이므로 정지조건이 없으면 무한 반복하게 된다.
이 때 두 값이 같으므로 해당 값을 그냥 반환해도 되지만,
코드를 짧게 유지하기 위해서 한 번 더 값을 체크하도록 한다.

이는 최소값 탐색에서도 달라지지 않는다.

구간의 크기가 2

가령 [1, 2]의 경우, mid = 1이다.
check()를 만족하는 경우 다시 [1, 2] 구간을 탐색할 것이고, 이는 무한루프로 빠지는 원인이 된다.
이 때 1만이 값을 만족할 수도 있고, 2 또한 값을 만족할 수도 있다.
따라서 2를 먼저 체크하고, 2가 만족시키는 경우 해의 범위 중 최대값이 2이므로 이것을 반환하면 된다.
그렇지 않은 경우 문제의 조건에 따라 1이 반드시 해가 될 것이므로 이를 반환하면 된다.

최소값 탐색의 경우 반대로 하면 된다.
s를 먼저 체크한 뒤 만족하면 s를 리턴하고, 아닌 경우 e가 답일 것이다.