이진 탐색 - 알고리즘카

문제. $1$부터 $100$ 사이의 정수 $x$가 하나 정해져 있으며, 여러분은 예/아니오로 답하는 질문으로 이 수를 맞혀야 합니다. 예를 들어 수 $x$가 주어진 수보다 큰지, 또는 짝수인지를 물어볼 수 있습니다. 최악의 경우 몇 번의 질문으로 수 $x$를 찾을 수 있습니까?

최적의 풀이 중 하나는 다음과 같은 구조입니다. 첫 번째 질문으로 「수 $x$가 50보다 큰가」를 묻고, 답이 「예」라면 다음으로 「수 $x$가 75보다 큰가」를, 그렇지 않다면 「수 $x$가 25보다 큰가」를 묻습니다. 이를 계속 반복하며, 매번 가능한 값의 구간을 절반(또는 거의 절반)으로 줄여 나갑니다.

좀 더 체계적으로 말하면, 탐색 구간이 있을 때(처음에는 $l=1$부터 $r=100$까지) 매 반복마다 「가운데」 원소 $m = \lfloor \frac{l+r}{2} \rfloor$를 고르고, 「$x>m?$」라고 묻고, 답에 따라 $l = m + 1$ 또는 $r = m$으로 대입한 뒤, 두 경계가 같아질 때까지(이는 $l = r = x$임을 뜻합니다) 새로운 경계로 이 과정을 반복합니다.

다음은 콘솔에서 실행할 수 있는 그러한 프로그램의 예입니다:

l, r = 1, 100

while l < r:
    m = (l + r) // 2
    resp = input(f'x > {m}? ')
    if resp == 'yes':
        l = m + 1
    else:
        r = m

print(f'x = {l}')

$x=42$를 정하고 질문에 정직하게 답하면 다음과 같습니다.

x > 50? no
x > 25? yes
x > 38? yes
x > 44? no
x > 41? yes
x > 43? no
x > 42? no
x = 42

여기서는 7번의 질문이 필요했지만, 정한 수에 따라 어떤 때는 정확히 $7$번, 어떤 때는 $6$번 질문하게 됩니다.

일반적으로 각 반복마다 탐색 구간의 길이가 반드시 절반으로 줄어들기 때문에(올림이 될 수도 있습니다) $O(\log n)$번의 연산이 필요하며, 더 정확히는 $\lceil \log_2 n \rceil$번 또는 $\lfloor \log_2 n \rfloor$번이 필요합니다.

#자료 구조에서

배열 $a$가 주어지고, 그 안에 원소 $x$가 있는지 판별해야 한다고 합시다.

분명히 최악의 경우에는 이 원소가 배열에 없지만, 이를 확인하려면 배열의 모든 원소를 살펴보는 데 $O(n)$번의 연산을 들여야 합니다.

그러나 배열이 정렬되어 있다면 배열에서 수 $x$를 더 빠르게 찾을 수 있습니다. 같은 방식으로 하한(영어: lower bound), 즉 $x$보다 작지 않은 가장 작은 수를 찾은 다음, 그 수가 $x$와 같은지 확인하면 됩니다.

bool find(int x, int *a, int n) {
    int l = 0, r = n + 1;
    // отрезок поиска теперь полуинтервал: [l, r)
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (a[m] >= x)
            l = m;
        else
            r = m;
    }
    return (l < n && a[l] == x);
}

표준 STL 컨테이너에는 이러한 함수가 구현되어 있습니다:

bool find(x, vector<int> a) {
    auto it = lower_bound(a.begin(), a.end(), x);
    return (it != a.end() && *it == x);
}

또한 C++에는 인수보다 엄밀히 큰 첫 번째 원소를 찾는 upper_bound 함수도 있습니다.

#속성 검사

이러한 방법은 원소를 찾는 데뿐만 아니라, 처음에는 성립하다가 이후에는 성립하지 않거나 그 반대인 어떤 단조적인 성질을 확인하는 데에도 일반화됩니다.

배열에서 하한을 찾는 것은 그 특수한 경우입니다. 조건 $(a[k] \geq x)$를 확인하면서, 어떤 $k$부터 이 조건이 성립하는지를 찾고자 합니다.

다른 예시:

정렬된 배열에서 $x$와 같은 마지막 수를 찾거나, 그러한 수가 없음을 출력하십시오.
정렬된 배열에서 수 $x$가 몇 번 나타나는지 세십시오.
수 배열이 주어지며, 앞부분은 홀수로, 뒷부분은 짝수로 이루어져 있습니다. 그 위치부터 모든 수가 짝수가 되는 인덱스를 찾으십시오.

이 모든 문제는 이진 탐색으로 $O(\log{n})$에 해결됩니다. 다만 이러한 문제를 순수한 형태 그대로 이진 탐색으로 푸는 것은 무의미하다는 점을 이해해야 합니다. 크기가 $n$인 배열을 만드는 데만 해도 이미 $O(n)$번의 연산이 필요하기 때문입니다.

그래서 이러한 문제는 흔히 다음과 같이 주어집니다. 크기가 $n$인 정렬된 배열이 주어집니다. “수 $x_i$가 배열에 존재하는가?” 형태의 질의 $m$개에 답해야 합니다. 이러한 문제는 $O(n + m\log{n})$에 해결됩니다. 먼저 $O(n)$에 배열을 만든 다음, 이진 탐색을 $m$번 실행하면 됩니다.

#실수 인자에 대한 이진 탐색

우리에게는 여전히 처음에는 0이다가 이후에 1이 되는 술어 함수 $f(x)$가 있으며, 우리는 그 값이 바뀌는 지점을 찾고자 합니다. 하지만 이제 함수의 인자는 실수입니다.

이러한 함수의 예는 다음과 같습니다.

$$ f(x) = \begin{cases} 0, & x^2 < 2 \\ 1, & x^2 \geq 2 \end{cases} $$

$x < \sqrt 2$일 때 $f(x) = 0$이고, 그보다 조금이라도 큰 값에서는 $f(x) = 1$입니다. 어떤 작은 $\epsilon$에 대해 $f(x_0) = 0$이고 $f(x_0 + \epsilon) = 1$인 $x_0$을 찾을 수 있다면, 2의 제곱근을, 나아가 다른 어떤 양수의 제곱근이든 계산할 수 있게 됩니다.

여기에서도 마찬가지로 이진 탐색을 적용할 수 있지만, 안타깝게도 문제가 생깁니다. 실수는 컴퓨터에 정확하게 저장되지 않습니다.

# известный пример
print(0.1 + 0.1 + 0.1)
# = 0.30000000000000004

더욱이 $\sqrt 2$의 정확한 값은 찾을 수 없습니다. 이는 무한 비순환 소수이기 때문입니다.

따라서 실수 인자에 대한 이진 탐색을 구현할 때는 신중하게 접근해야 합니다.

$f(l_0) = 0$이고 $f(r_0) = 1$인지 확인해야 합니다.
$r - l < \epsilon$이 되면 멈추거나, (더 나은 방법으로) 고정된 횟수만큼 반복을 수행해야 합니다.

정답 자릿수 $k$개를 얻으려면 몇 번의 반복이 필요하겠습니까? 이진 탐색은 이진 로그 시간에 동작하므로, 수의 십진 자릿수 하나를 맞히는 데 이진 탐색 약 세 단계가 필요하다고 할 수 있습니다($\log 10 \approx 3$). 따라서 예를 들어 함수값을 소수점 아래 여섯 자리까지 계산해야 한다면, $l$과 $r$ 사이의 거리가 1에 도달한 뒤에도 약 18단계가 더 필요합니다.

매번 이것을 고민하지 않도록, 이진 탐색을 100단계 수행하면 모든 합리적인 목적에 항상 충분하다고 생각해도 됩니다:

float sqrt(float x) {
    float l = 0, r = x;
    for (int i = 0; i < 100; i++) {
        float m = (l + r) / 2;
        if (m * m < x)
            l = m;
        else
            r = m;
    }
    return l;
}

사실 이 방법으로는 함숫값이 0보다 작아지는 인자 값과 0보다 커지는 인자 값을 알고 있는 연속 함수라면 어떤 함수든 그 영점을 찾을 수 있습니다(방금 우리는 함수 $x^2 - 2$의 영점을 찾았습니다).