이진 탐색¶

이진 탐색은 탐색 구간을 둘로 나누어 무언가를 더 빠르게 찾을 수 있게 해 주는 방법입니다. 가장 흔한 용도는 정렬된 배열에서 값을 찾는 것이지만, 구간을 나누는 아이디어는 다른 많은 전형적인 문제에서도 매우 중요합니다.

정렬된 배열에서의 탐색¶

이진 탐색으로 이어지는 가장 전형적인 문제는 다음과 같습니다. 정렬된 배열 $A_0 \leq A_1 \leq \dots \leq A_{n-1}$이 주어질 때, $k$가 이 수열 안에 있는지 확인하십시오. 가장 단순한 풀이는 모든 원소를 하나씩 확인하며 $k$와 비교하는 것입니다(이른바 선형 탐색). 이 방법은 $O(n)$에 동작하지만, 배열이 정렬되어 있다는 사실을 활용하지 못합니다.

배열에서 값 $7$을 이진 탐색하는 과정.
이 이미지는 작성자 AlwaysAngry 의 저작물로, CC BY-SA 4.0 라이선스에 따라 배포됩니다.

이제 $A_L \leq k \leq A_R$를 만족하는 두 인덱스 $L < R$를 알고 있다고 가정합시다. 배열이 정렬되어 있으므로, $k$는 $A_L, A_{L+1}, \dots, A_R$ 중에 나타나거나 배열에 전혀 나타나지 않는다고 추론할 수 있습니다. $L < M < R$를 만족하는 임의의 인덱스 $M$을 골라 $k$가 $A_M$보다 작은지 큰지 확인한다고 합시다. 가능한 경우는 두 가지입니다:

$A_L \leq k \leq A_M$. 이 경우 문제를 $[L, R]$에서 $[L, M]$으로 줄입니다;
$A_M \leq k \leq A_R$. 이 경우 문제를 $[L, R]$에서 $[M, R]$로 줄입니다.

$M$을 고를 수 없을 때, 즉 $R = L + 1$일 때는 $k$를 $A_L$ 및 $A_R$와 직접 비교합니다. 그렇지 않으면 최악의 경우에 활성 구간을 가능한 한 빨리 원소 하나로 줄일 수 있도록 $M$을 고르고자 합니다.

최악의 경우에는 항상 $[L, M]$과 $[M, R]$ 중 더 큰 구간으로 줄어들기 때문입니다. 따라서 최악의 경우 구간의 크기는 $R-L$에서 $\max(M-L, R-M)$로 줄어듭니다. 이 값을 최소화하려면 $M \approx \frac{L+R}{2}$를 골라야 하며, 그러면

$$ M-L \approx \frac{R-L}{2} \approx R-M. $$

즉, 최악의 경우를 기준으로 보면 항상 $[L, R]$의 한가운데에서 $M$을 골라 구간을 절반으로 나누는 것이 최적입니다. 따라서 활성 구간은 크기가 $1$이 될 때까지 매 단계마다 절반으로 줄어듭니다. 따라서 이 과정에 $h$단계가 필요하다면, 최종적으로 $R$과 $L$의 차이는 $R-L$에서 $\frac{R-L}{2^h} \approx 1$로 줄어들며, 이로부터 방정식 $2^h \approx R-L$을 얻습니다.

양변에 $\log_2$를 취하면 $h \approx \log_2(R-L) \in O(\log n)$을 얻습니다.

로그 규모의 단계 수는 선형 탐색의 단계 수보다 훨씬 좋습니다. 예를 들어 $n \approx 2^{20} \approx 10^6$일 때 선형 탐색으로는 약 백만 번의 연산을 수행해야 하지만, 이진 탐색으로는 약 $20$번의 연산만 수행하면 됩니다.

하한과 상한¶

원소의 정확한 위치보다는 $k$보다 크거나 같은 첫 번째 원소의 위치(배열에서 $k$의 하한(lower bound)이라고 합니다)나 $k$보다 큰 첫 번째 원소의 위치($k$의 상한(upper bound)이라고 합니다)를 찾는 것이 편리한 경우가 많습니다.

하한과 상한을 함께 사용하면 $k$와 같은 배열 원소들로 이루어진, 비어 있을 수도 있는 반구간을 얻습니다. $k$가 배열에 있는지 확인하려면 $k$의 하한을 찾고 해당 원소가 $k$와 같은지 확인하는 것으로 충분합니다.

구현¶

위의 설명은 알고리즘을 대략적으로 기술한 것입니다. 구현 세부 사항을 다루려면 더 정확하게 정의할 필요가 있습니다.

$A_L \leq k < A_R$을 만족하는 쌍 $L < R$을 유지하겠습니다. 즉, 활성 탐색 구간은 $[L, R)$입니다. 여기서 구간 $[L, R]$ 대신 반구간을 사용하는 이유는 그렇게 하는 편이 예외 상황 처리가 덜 필요하기 때문입니다.

$R = L+1$일 때, 위의 정의로부터 $R$이 $k$의 상한임을 알 수 있습니다. $R$은 끝을 지난 인덱스, 즉 $R=n$으로, $L$은 시작 이전의 인덱스, 즉 $L=-1$로 초기화하는 것이 편리합니다. 알고리즘에서 $A_L$과 $A_R$을 직접 계산하지 않는 한 이는 문제가 없으며, 형식적으로는 $A_L = -\infty$, $A_R = +\infty$로 취급합니다.

마지막으로, 선택하는 $M$의 값을 구체적으로 정하기 위해 $M = \lfloor \frac{L+R}{2} \rfloor$을 사용하겠습니다.

그러면 구현은 다음과 같을 수 있습니다:

... // a sorted array is stored as a[0], a[1], ..., a[n-1]
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (k < a[m]) {
        r = m; // a[l] <= k < a[m] <= a[r]
    } else {
        l = m; // a[l] <= a[m] <= k < a[r]
    }
}

알고리즘이 실행되는 동안 $L < M < R$이므로 $A_L$도 $A_R$도 계산하지 않습니다. 결국 $L$은 $k$보다 크지 않은 마지막 원소의 인덱스(그러한 원소가 없으면 $-1$)가 되고, $R$은 $k$보다 큰 첫 번째 원소의 인덱스(그러한 원소가 없으면 $n$)가 됩니다.

참고. m을 m = (r + l) / 2로 계산하면 l과 r이 둘 다 양의 정수일 때 오버플로가 발생할 수 있으며, 블로그 글에 설명된 것처럼 이 오류는 JDK에 약 9년 동안 남아 있었습니다. 대안으로는 예를 들어 m = l + (r - l) / 2로 작성하는 방법이 있는데, 이는 양의 정수 l과 r에 대해서는 항상 동작하지만 l이 음수이면 여전히 오버플로가 발생할 수 있습니다. C++20을 사용한다면 항상 올바르게 동작하는 m = std::midpoint(l, r)이라는 대안을 쓸 수 있습니다.

임의의 술어에 대한 탐색¶

$f : \{0,1,\dots, n-1\} \to \{0, 1\}$을 $0,1,\dots,n-1$에서 정의된, 단조 증가하는 불리언 함수라고 합시다. 즉,

$$ f(0) \leq f(1) \leq \dots \leq f(n-1). $$

위에서 설명한 방식의 이진 탐색은 $k < A_M$ 식의 불리언 값을 갖는 술어 $f(M)$에 따라 배열의 분할을 찾습니다. $k < A_M$ 대신 임의의 단조 술어를 사용할 수도 있습니다. 이는 가능한 모든 값에 대해 $f(k)$를 실제로 계산하기에는 시간이 너무 많이 드는 경우에 특히 유용합니다. 다시 말해, 이진 탐색은 그러한 전이 지점이 존재하면 $f(L) = 0$이고 $f(R)=f(L+1)=1$인 유일한 인덱스 $L$을 찾고, $f(0) = \dots = f(n-1) = 0$이면 $L = n-1$을, $f(0) = \dots = f(n-1) = 1$이면 $L = -1$을 돌려줍니다.

전이점이 존재한다고, 즉 $f(0)=0$이고 $f(n-1)=1$이라고 가정할 때의 정확성 증명: 이 구현은 루프 불변식 $f(l)=0, f(r)=1$을 유지합니다. $r - l > 1$일 때, $m$을 선택하는 방식 때문에 $r-l$은 항상 감소합니다. 루프는 $r - l = 1$일 때 종료되며, 이로써 원하는 전이점을 얻습니다.

... // f(i) is a boolean function such that f(0) <= ... <= f(n-1)
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (f(m)) {
        r = m; // 0 = f(l) < f(m) = 1
    } else {
        l = m; // 0 = f(m) < f(r) = 1
    }
}

답에 대한 이진 탐색¶

이러한 상황은 어떤 값을 계산해야 하지만 그 값이 $i$ 이상인지 여부만 확인할 수 있을 때 자주 발생합니다. 예를 들어, 배열 $a_1,\dots,a_n$이 주어지고, 다음과 같은 내림한 평균 합의 최댓값을

$$ \left \lfloor \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \right\rfloor $$

$r-l \geq x$를 만족하는 모든 가능한 $l,r$ 쌍 중에서 구해야 한다고 합시다. 이 문제를 푸는 간단한 방법 중 하나는 답이 $\lambda$ 이상인지, 즉 다음이 성립하는 $l, r$ 쌍이 존재하는지 확인하는 것입니다.

$$ \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \geq \lambda. $$

이는 다음과 같이 동치로 다시 쓸 수 있습니다.

$$ (a_l - \lambda) + (a_{l+1} - \lambda) + \dots + (a_r - \lambda) \geq 0, $$

따라서 이제 새 배열 $a_i - \lambda$에서 길이가 $x+1$ 이상이고 합이 음이 아닌 부분 배열이 존재하는지 확인하면 되며, 이는 누적 합을 이용하여 할 수 있습니다.

연속 탐색¶

$f : \mathbb R \to \mathbb R$를 구간 $[L, R]$에서 연속인 실숫값 함수라고 합시다.

일반성을 잃지 않고 $f(L) \leq f(R)$이라고 가정합니다. 중간값 정리에 의해 임의의 $y \in [f(L), f(R)]$에 대해 $f(x) = y$를 만족하는 $x \in [L, R]$가 존재합니다. 앞의 단락들과 달리, 이 함수는 단조일 필요가 없다는 점에 주의하십시오.

값 $x$는 임의의 특정한 $\delta$ 값에 대해 $O\left(\log \frac{R-L}{\delta}\right)$ 시간에 $\pm\delta$ 이내로 근사할 수 있습니다. 아이디어는 본질적으로 같습니다. $M \in (L, R)$을 잡으면, $f(M)$이 $y$보다 큰지 여부에 따라 탐색 구간을 $[L, M]$ 또는 $[M, R]$ 중 하나로 줄일 수 있습니다. 여기서 흔한 예로는 홀수 차수 다항식의 근을 찾는 것이 있습니다.

예를 들어, $f(x)=x^3 + ax^2 + bx + c$라고 합시다. 그러면 $L \to -\infty$이고 $R \to +\infty$일 때 $f(L) \to -\infty$이고 $f(R) \to +\infty$입니다. 이는 $f(L) < 0$이고 $f(R) > 0$을 만족하는 충분히 작은 $L$과 충분히 큰 $R$을 항상 찾을 수 있다는 뜻입니다. 그러면 이진 탐색을 사용하여 $f(x)=0$을 만족하는 $x$를 포함하는 임의로 작은 구간을 찾을 수 있습니다.

2의 거듭제곱을 이용한 탐색¶

이진 탐색을 수행하는 또 다른 주목할 만한 방법은 활성 구간을 유지하는 대신 현재 포인터 $i$와 현재 거듭제곱 $k$를 유지하는 것입니다. 포인터는 $i=L$에서 시작하며, 각 반복마다 점 $i+2^k$에서 판정 조건을 검사합니다. 판정 조건이 여전히 $0$이면 포인터를 $i$에서 $i+2^k$로 전진시키고, 그렇지 않으면 그대로 둔 다음, 지수 $k$를 $1$만큼 감소시킵니다.

이 패러다임은 두 정점의 최소 공통 조상을 찾거나 특정 정점의 조상 중 특정 높이를 가진 조상을 찾는 등 트리와 관련된 문제에서 널리 사용됩니다. 또한 예를 들어 펜윅 트리에서 $k$번째 0이 아닌 원소를 찾는 데에도 응용할 수 있습니다.

병렬 이진 탐색¶

각각 이진 탐색으로 풀 수 있는 쿼리가 여러 개 주어질 때, 이를 하나씩 푸는 것은 때때로 너무 느립니다. 병렬 이진 탐색은 이러한 모든 쿼리를 동시에 풀 수 있게 해 주는 기법으로, 상당한 성능 향상으로 이어지는 경우가 많습니다. 핵심 아이디어는 모든 쿼리에 대한 이진 탐색을 동시에(병렬로) 한 단계씩 수행하는 것입니다. 이는 이진 탐색의 판정 함수가 비용이 크고 쿼리를 일괄 처리하여 최적화할 수 있을 때 특히 효과적입니다.

$Q$개의 쿼리가 있고, 각 쿼리 $q$에 대해 어떤 조건 $P(q, x)$를 만족하는 가장 작은 값 $x$를 찾아야 하는 상황을 생각해 봅시다. $P(q, x)$가 $x$에 대해 단조적이라면 각 쿼리에 이진 탐색을 사용할 수 있습니다. 이렇게 하면 전체 복잡도는 $O(Q \cdot \log(range) \cdot T_{check})$가 되며, 여기서 $T_{check}$는 $P(q, x)$를 평가하는 데 드는 시간입니다.

병렬 이진 탐색은 연산 순서를 바꾸어 이를 최적화합니다. 각 쿼리를 독립적으로 처리하는 대신, 모든 쿼리를 동시에 한 단계씩 처리합니다. 이진 탐색의 각 단계에서 모든 쿼리에 대한 중간점 $m_i$를 계산하고, 쿼리를 중간점별로 묶습니다. 이 방법은 판정 함수 $P(q, x)$가 효율적인 일괄 처리나 갱신을 허용하는 구조를 가질 때 특히 강력합니다.

구체적으로, 주요 성능 향상은 다음 두 가지 경우에서 나옵니다.

비용이 큰 판정의 일괄 처리: 어떤 단계에서 여러 쿼리가 같은 값 $m$을 판정해야 한다면, 판정에서 비용이 큰 부분을 한 번만 수행하고 그 결과를 재사용할 수 있습니다.
효율적으로 갱신 가능한 판정: 값 $m$에 대한 판정(예: "처음 $m$개의 이벤트를 처리")은 $m-1$에 대한 상태를 이미 계산해 두었다면 훨씬 빠르게 수행할 수 있는 경우가 많습니다. 판정 값 $m$을 오름차순으로 처리하면, 매번 처음부터 다시 계산하는 대신 한 판정에서 다음 판정으로 상태를 갱신해 나갈 수 있습니다. 이는 시간이나 일련의 갱신이 관련된 문제에서 매우 흔한 패턴입니다.

모든 쿼리를 모은 뒤 자료 구조에 편리한 방식으로 한꺼번에 답하는 이러한 쿼리의 "오프라인" 처리가 병렬 이진 탐색의 핵심 아이디어입니다.

구현¶

정렬된 0-인덱스 배열 $A$에서 어떤 $X_i$($i=1,2,\ldots,Z$) 이하인 가장 큰 값의 인덱스를 묻는 쿼리 $Z$개에 답하고자 한다고 가정해 봅시다. 당연히 각 쿼리는 이진 탐색을 사용하여 답할 수 있습니다.

구체적으로, 다음 배열 $A = [1,3,5,7,9,9,13,15]$와 쿼리 $X = [8,11,4,5]$를 생각해 봅시다. 각 쿼리에 대해 순차적으로 이진 탐색을 사용할 수 있습니다.

쿼리	$ X_1 = 8 $	$ X_2 = 11 $	$ X_3 = 4 $	$ X_4 = 5 $
1단계	답의 범위: $[0,8)$ $ A_4 $ 확인 $ X_1 < A_4 = 9 $	답의 범위: $[0,8)$ $ A_4 $ 확인 $ X_2 \geq A_4 = 9 $	답의 범위: $[0,8)$ $ A_4 $ 확인 $ X_3 < A_4 = 9 $	답의 범위: $[0,8)$ $ A_4 $ 확인 $ X_4 < A_4 = 9 $
2단계	답의 범위: $[0,4)$ $ A_2 $ 확인 $ X_1 \geq A_2 = 5 $	답의 범위: $[4,8)$ $ A_6 $ 확인 $ X_2 < A_6 = 13 $	답의 범위: $[0,4)$ $ A_2 $ 확인 $ X_3 < A_2 = 5 $	답은 $[0,4)$에 있습니다 $ A_2 $ 확인 $ X_4 \geq A_2 = 5 $
3단계	답은 $[2,4)$에 있습니다 $ A_3 $ 확인 $ X_1 \geq A_3 = 7 $	답은 $[4,6)$에 있습니다 $ A_5 $ 확인 $ X_2 \geq A_5 = 9 $	답은 $[0,2)$에 있습니다 $ A_1 $ 확인 $ X_3 \geq A_1 = 3 $	답은 $[2,4)$에 있습니다 $ A_3 $ 확인 $ X_4 < A_3 = 7 $
4단계	답은 $[3,4)$에 있습니다 $ index = 3 $	답은 $[5,6)$에 있습니다 $ index = 5 $	답은 $[1,2)$에 있습니다 $ index = 1 $	답은 $[2,3)$에 있습니다 $ index = 2 $

일반적으로 이 표는 열(쿼리) 단위로 처리하지만, 각 행에서 배열의 특정 값에 반복해서 접근하는 경우가 많다는 점에 주목하십시오. 이러한 값에 대한 접근을 줄이기 위해 표를 행(단계) 단위로 처리할 수 있습니다. 우리의 작은 예제 문제에서는 (모든 원소에 $O(1)$에 접근할 수 있으므로) 큰 차이가 없지만, 이러한 값을 계산하는 것이 더 복잡한 문제에서는 이 방식이 문제를 효율적으로 해결하는 데 필수적일 수 있습니다. 또한 한 행 안에서는 질문에 답하는 순서를 임의로 정할 수 있다는 점에 유의하십시오. 이 접근법을 구현한 코드를 살펴봅시다.

// Computes the index of the largest value in a sorted array A less than or equal to X_i for all i.
vector<int> parallel_binary_search(vector<int>& A, vector<int>& X) {
    int N = A.size();
    int Z = X.size();
    vector<int> l(Z, -1), r(Z, N);

    for (int step = 1; step <= ceil(log2(N + 1)); ++step) {
        // A vector of vectors to store indices of queries for each middle point.
        vector<vector<int>> m_to_queries(N);

        // Group queries by their middle point.
        for (int i = 0; i < Z; ++i) {
            if (l[i] < r[i] - 1) {
                int m = l[i] + (r[i] - l[i]) / 2;
                m_to_queries[m].push_back(i);
            }
        }

        // Process each group of queries.
        for (int m = 0; m < N; ++m) {
            if (m_to_queries[m].empty()) {
                continue;
            }
            for (int query : m_to_queries[m]) {
                if (X[query] < A[m]) {
                    r[query] = m;
                } else {
                    l[query] = m;
                }
            }
        }
    }
    return l;
}

예제 풀이: Meteors

이 방법을 사용하는 꽤 잘 알려진 문제로 "Meteors"가 있으며, 연습 문제 목록에 포함되어 있습니다. $N$개의 나라가 주어지고, 각 나라마다 모아야 하는 운석의 목표 개수가 주어집니다. 또한 $K$개의 유성우로 이루어진 수열이 주어지며, 각 유성우는 나라들의 한 구간에 영향을 줍니다. 목표는 각 나라에 대해 목표치에 도달하는 가장 이른 시점(즉, 몇 번째 유성우인지)을 찾는 것입니다.

한 국가에 대해서는 $1$부터 $K$까지 답을 이진 탐색할 수 있습니다. 주어진 시점 $t$에 대한 확인은 그 나라에 대해 처음 $t$개의 유성우로 떨어진 운석을 모두 더하는 작업입니다. 단순하게 확인하면 $O(t)$ 시간이 걸리므로, 한 나라에 대해 전체 복잡도가 $O(K \log K)$, 모든 나라에 대해서는 $O(N \cdot K \log K)$가 되어 너무 느립니다.

병렬 이진 탐색을 사용하면 $N$개 국가 모두에 대한 답을 한꺼번에 탐색합니다. $O(\log K)$개의 각 단계에서는 나라들에 대한 확인값 $t_i$의 집합이 있습니다. 이 $t_i$들을 오름차순으로 처리할 수 있습니다. 시점 $t$에 대한 확인을 수행하기 위해 펜윅 트리나 세그먼트 트리 같은 자료 구조를 사용하여 모든 나라의 운석 개수를 관리할 수 있습니다. 시점 $t_i$의 확인에서 $t_{i+1}$의 확인으로 넘어갈 때는 $t_i+1$부터 $t_{i+1}$까지의 유성우 효과만 자료 구조에 더하면 됩니다. 이러한 "갱신" 방식은 처음부터 다시 계산하는 것보다 훨씬 빠릅니다. 전체 복잡도는 $O((N+K)\log N \log K)$가 됩니다.

이진 탐색¶

정렬된 배열에서의 탐색¶

하한과 상한¶

구현¶

임의의 술어에 대한 탐색¶

답에 대한 이진 탐색¶

연속 탐색¶

2의 거듭제곱을 이용한 탐색¶

병렬 이진 탐색¶

구현¶

연습 문제¶

이진 탐색¶

병렬 이진 탐색¶