이분 탐색 잘 하는 법

백준 블로그에서 본 글을 재구성한 글이고, 백준이 날라가서 임시로 작성한 글임. 누가 쓰셨는진 모르겠는데 알려주시면 출처 남김

레드가 아니면 이분 탐색이나 공부하라는 엄닉 센세의 말을 잘 새겨들을 것.

문제 단순화

수열 $a_1, a_2, \dots, a_n$이 있고 $a_x \ne a_{x + 1}$를 만족하는 정수 $x$가 유일할 때 정수 $x$를 찾으시오.

방법론

$\text{lo} = 1$, $\text{hi} = n$라는 변수를 선언한다.

$\text{lo} + 1 = \text{hi}$가 되기 전까지 다음을 반복한다:

$\text{mi} = \lfloor \frac{\text{lo} + \text{hi}}{2} \rfloor$라고 정의하고, $a_{\text{lo}} = a_{\text{mi}}$라면 $\text{lo} \coloneqq \text{mi}$를, 아니면 $\text{hi} \coloneqq \text{mi}$를 수행한다.

정당성

$a_{\text{lo}} = a_1$, $a_{\text{hi}} = a_n$가 유지되므로 $a_{\text{lo}} \ne a_{\text{hi}}$도 유지된다.

따라서 $\text{lo} + 1 = \text{hi}$가 되었다면 $x = \text{lo}$임을 알 수 있다.

코드

int lo = 1, hi = n;
while (lo + 1 < hi) {
    int mi = (lo + hi) / 2;
    (a[lo] == a[mi] ? lo : hi) = mi;
}

적용

이 방법을 여러 문제에 적용하기 위해서는, 우선 값을 두 가지 종류로 변환해야 한다.

예를 들어, 증가하는 수열 $b_1, b_2, \dots, b_n$에 값 $v$가 존재하는지, 존재한다면 어느 위치에 존재하는지 찾고 싶을 수 있다.

수열 $a_0, a_1, \dots, a_{n+1}$에 대해 $a_0 = \text{false}$, $a_i = (b_i \geq v)$, $a_{n+1} = \text{true}$라 정의하고 위에서 설명한 이분 탐색을 수행하자.

처음으로 $b_x \geq v$가 되는 위치 $x$를 찾을 수 있는데, $x < n + 1$인지, $b_x = v$인지 정도만 체크하면 수열에 $v$가 존재하는지와 어느 위치에 존재하는지를 찾을 수 있다.

이와 같이 거의 모든 이분 탐색 문제는 값을 두 종류로 변환함으로써 이 방법론을 적용할 수 있다.