Algorithms/Binary & Parametric Search

2.11.1 Binary Search

개념

이분 탐색은 정렬된 구간에서 가운데 값을 확인하고 탐색 범위를 절반으로 줄입니다. 목표값보다 작으면 오른쪽을, 크면 왼쪽을 탐색합니다.

예를 들어 [1,3,5,7,9][1,3,5,7,9]에서 77을 찾을 때 가운데 값 55를 확인합니다. 왼쪽의 값들은 모두 55 이하이므로 77이 있을 수 없고, 55와 그 왼쪽을 한 번에 제외할 수 있습니다. 이 판단은 수열이 정렬되어 있다는 성질에 의존합니다.

원소가 100000100000개여도 범위를 절반씩 줄이면 약 1717번의 축소로 후보를 좁힐 수 있습니다. 이미 정렬된 데이터에서 여러 번 값을 찾을 때 유용합니다. 정렬되지 않은 데이터라면 먼저 정렬하는 비용까지 함께 계산합니다.

경계 찾기

Lower Bound는 목표값 이상인 첫 위치입니다. Upper Bound는 목표값을 초과하는 첫 위치입니다. 해당 위치가 없으면 배열 길이를 반환합니다. 두 위치의 차이는 목표값의 등장 횟수입니다.

[1,2,2,2,5][1,2,2,2,5]에서 22의 Lower Bound는 11, Upper Bound는 44이므로 등장 횟수는 33입니다.

Lower Bound에서는 가운데 값이 목표보다 작으면 그 값과 왼쪽 부분을 제외할 수 있습니다. 가운데 값이 목표 이상이면 그 위치가 답일 수도 있지만, 왼쪽에도 목표 이상인 값이 있을 수 있으므로 왼쪽 경계를 계속 찾습니다. 이 과정을 통해 같은 값 중 첫 위치를 찾습니다.

Upper Bound는 목표와 같은 값도 지나쳐서 처음으로 더 큰 값이 나오는 경계를 찾습니다. 두 경계 사이에는 목표와 같은 값만 있으므로, 경계 위치의 차이가 등장 횟수입니다.

동작C++JavaPython
Lower Boundlower_bound경계 탐색 직접 구현bisect_left
Upper Boundupper_bound경계 탐색 직접 구현bisect_right

복잡도

Java의 Arrays.binarySearch는 같은 값이 여러 개일 때 첫 위치를 보장하지 않으므로 경계 탐색과 구분합니다. 원소 수를 NN이라고 합니다.

연산시간복잡도공간복잡도
이분 탐색·경계 탐색O(log⁡N)O(\log N)추가 O(1)O(1)

예제

문제

정렬된 수열에서 주어진 값이 몇 번 나오는지 구하여라.

입력

첫째 줄에 원소 수 NN과 찾을 값 XX가 공백을 사이에 두고 주어진다. 1≤N≤1 0001\le N\le1\,000; 1≤X<10 0001\le X<10\,000이다.

둘째 줄에 수열의 원소 a1,a2,…,aNa_1,a_2,\ldots,a_N이 공백을 사이에 두고 주어진다. 1≤ai<10 0001\le a_i<10\,000이다. 원소는 오름차순으로 정렬되어 있다.

출력

XX의 등장 횟수를 출력한다.

예제 입력

5 2
1 2 2 2 5

예제 출력

3

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> v;

int main() {
    int n, x, i, l, r;

    cin >> n >> x;
    v.resize(n);
    for (i = 0; i < n; ++i) {
        cin >> v[i];
    }
    l = lower_bound(v.begin(), v.end(), x) - v.begin();
    r = upper_bound(v.begin(), v.end(), x) - v.begin();
    cout << r - l << '\n';
}