이분탐색 (Binary Search)

이분탐색

말 그대로 두개로 나누어서 탐색하는 방식이다. 정확히는 정렬된 데이터에서 절반인 지점을 찍어 찾는 데이터가 맞는지 확인하는 과정을 계속해서 거쳐서 원하는 데이터를 찾는 방식이다.

Up Down 게임

Up Down 게임을 생각하면 이해가 좀 더 쉬울 것이다. 상대방이 1부터 100사이의 수 중에 하나를 선택하고 우리는 턴마다 숫자를 물어봐서 선택한 수와 (동일한지 / 큰지 / 작은지)를 알 수 있다.

여기서 1, 2, 3, 4, ... 이렇게 차례대로 부른다면 언젠가는 맞겠지만 우리는 이 턴을 최대한 줄이고 싶다. 운이 좋으면 한 번에 맞출 수도 있겠지만 여러번의 게임을 진행했을 때를 고려하자.

이 게임을 어떻게 플레이할지는 모두 알 것이다. 50을 찍고 Up 이면 51과 100의 절반인 75, 75보다 작다면 51과 74의 절반인 62, 이렇게 답의 범위를 줄여나갈 것이다.

// 생각한 숫자: K
void UpDownGame() {
    int K = rand() % 100 + 1;
    int s = 1, e = 100;
    cout << "K: " << K << "\n";
    while (s <= e) {
        int mid = (s + e) / 2;
        cout << "QUERY: " << mid << "\n";
        if (K == mid) {
            cout << "CORRECT!\n";
            break;
        }
        else if (K > mid) {
            cout << "UP\n";
            s = mid + 1;
        }
        else {
            cout << "DOWN\n";
            e = mid - 1;
        }
    }
}

이런식으로 이분탐색을 구현하면 된다! 사고의 흐름과 일치하기에 금방 익숙해질 것이다.

데이터 찾기

그렇다면 다음과 같은 것도 할 수 있다. 아래와 같이 정렬된 수열이 있다. 인덱스는 1번부터 시작한다고 하자.
1 4 12 49 50 55 59 72 100 101 103 107 129

해당 수열에서 100이 몇 번째 인덱스에 있는지 확인해보자. 이를 확인하기 위한 방법으로는 맨 처음 인덱스부터 100이 맞는지 차례대로 확인해나가는 방법이 있다. 위의 Up Down 게임과 마찬가지로 꽤나 오랜 시간이 걸릴 수 있다.

다른 방법으로는 방금 배운 이분탐색을 이용하는 것이다. 수열의 길이가 13이므로 1부터 13의 절반인 6번째 인덱스가 100인지 비교하는 것이다.

55이다. 더 작으므로 7부터 13의 절반인 10번째 인덱스가 100인지 비교한다.

101이다. 더 크므로 7부터 9의 절반인 8번째 인덱스가 100인지 비교한다.

72이다. 더 작으므로 9부터 9의 절반인 9번째 인덱스가 100인지 비교한다.

100이다!

이렇게 탐색을 해야하는 범위가 절반씩 줄어드는 것을 볼 수 있다. 따라서 최대 $O(logN)$번의 탐색으로 원하는 값을 찾을 수 있음이 보장된다.

조건

여기까지 글을 읽었더라면 어떤 형태의 데이터가 이분탐색을 사용할 수 있는 데이터인지를 알 수 있을 것이다. 바로 정렬되어 있는(sorted) 데이터이다. "Up Down 게임도 그런가요?" 라고 할 수 있는데, 잘 생각해보면 1, 2, 3, ..., 100 이 나열된 수열에서 데이터 찾기 를 진행하는 것과 같다.

데이터를 정렬된 형태로 주는 경우도 있으나 그렇지 않은 경우도 많기 때문에 대부분은 전처리에서 데이터를 정렬하는데 $O(NlogN)$이 들긴 한다...

매개변수 탐색

이분탐색과 거의 동일하다. 구현 내용도 99% 일치한다. 단지 문제의 유형이 다를 뿐이다. 이분탐색은 나열된 데이터에서 크기 비교를 하면서 특정 데이터를 찾는 것이라면 매개변수 탐색은 값이 변경되는 경계면을 찾는 것이다.

한 사람이 14:03 에 머리를 깎았다고 하자. 다른 한 사람은 이 사람이 머리를 당일 깎은 것만 안다. Up Down 게임처럼 시간을 물어볼 것이다. 여기서의 대답은 해당 시간에서 머리가 깎여 있었는가에 대해 Y/N 로 답을 해준다.

이러한 상황도 00:00에서 23:59의 절반인 11:59를 물어본다.

N, 아직 깎지 않았으니 그 다음인 12:00에서 23:59의 절반인 17:59를 물어본다.

Y, 깎은 상태이므로 이전에 깎았음을 알 수 있다. 새로운 구간에서 절반을 물어보는 것을 반복한다.

여기서 Y의 대답을 받을 때마다 시간을 갱신해주면 된다.