이분 탐색(Binary Search)

이분탐색이 뭐에요

이분 탐색은 $N$개의 원소가 정렬되어 있을 때, 특정 원소 $x$를 $O(log N)$의 시간복잡도에 찾는 알고리즘입니다.

이분 탐색은 다음의 원리로 동작합니다.

• 원소들 중 가장 가운데 값을 $x$와 비교합니다. 편의상 가운데 값을 $mid$라고 하겠습니다.
• $mid$가 $x$보다 크다면 끝 위치를 가운데 위치-1로 바꿔서 진행합니다.
• $mid$가 $x$보다 작다면 시작 위치를 가운데 위치+1로 바꿔서 진행합니다.
• $mid$과 $x$가 같다면 알고리즘을 종료합니다.

시간 복잡도는 어떻게 돼요

한 단계가 진행될 때마다 범위가 $\frac{1}{2}$로 줄어드므로 시간복잡도를 $x$라고 하면,

$N \times (\frac{1}{2})^x = 1$

$2 ^ x = N$

$x = log N$

따라서 시간복잡도는 $O(log N)$이 됩니다.

구현은 어케 해요

구현은 반복문을 이용할 수도 있고, 재귀 함수를 이용할 수도 있습니다.

예시 코드1(반복문)

int BinarySearch(int A[], int x) {
    for(int s=1, e=N; s<=e; ) {
    	int mid=(s+e)/2;
        if(A[mid]>x) e=mid-1;
        else if(A[mid]<x) s=mid+1;
        else return mid;
    }
}

예시 코드2(재귀 함수)

int BinarySearch(int A[], int x, int s, int e) {
    int mid=(s+e)/2;
    if(A[mid]>x) return BinarySearch(A, x, s, mid-1);
    else if(A[mid]<x) return BinarySearch(A, x, mid+1, e);
    else return mid;
}

예시 1.

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

풀이

위에서 설명한 것처럼 이분 탐색을 이용하면 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int N,A[100010];
int M,Q;

bool BinarySearch(int s,int e,int k) {
    if(s>e) return 0;
    int mid=(s+e)/2;
    if(A[mid]>k) return Find(s,mid-1,k);
    else if(A[mid]<k) return Find(mid+1,e,k);
    else return 1;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++) cin>>A[i];
    sort(A+1,A+1+N);
    cin>>M;
    for(int i=1;i<=M;i++) {
        cin>>Q;
        cout<<Find(1,N,Q)<<"\n";
    }
    return 0;
}

파라메트릭 서치(Parametric Search)가 뭐에요

파라메트릭 서치는 이분탐색의 변형이라고 볼 수 있습니다.

파라메트릭 서치의 핵심은 "최적화 문제(최솟값/최댓값 등을 구하는 문제)를 결정 문제(O 또는 X를 구하는 문제)로 바꾸는 것"입니다.

잘 와닿지 않을 수 있으니 예제로 설명하겠습니다.

 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

$M$미터 이상의 나무를 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제입니다.

문제를 바꿔서, "절단기의 높이가 $x$일 때 $M$미터 이상의 나무를 가져갈 수 있는가?"라고 하면, $O(N)$에 해결할 수 있습니다.

이 문제의 답은 $x$가 어떤 수보다 작으면 X, 그 수보다 크거나 같으면 O일 것입니다.

그러므로 이분탐색과 비슷한 아이디어를 적용해 단계마다 탐색 구간을 $\frac{1}{2}$로 줄일 수 있습니다.

총 $log N$개의 단계가 있고, 각 단계마다 $O(N)$이 걸리므로, $O(N log N)$에 해결할 수 있습니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int Nmax=1000010,X=1e9;
int N, M;
int ans, a[Nmax];

bool f(int x) {
    ll sum=0;
    for(int i=1;i<=n;i++)
        sum+=max(0,a[i]-x);
    return res>=M;
}

void BinarySearch(int s,int e) {
    while(s<=e) {
        int mid=(s+e)/2;
        if(f(mid)) ans=mid, s=mid+1;
        else e=mid-1;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>a[i];
    BinarySearch(0,X);
    cout<<ans;
    return 0;
}

예시 2.

https://www.acmicpc.net/problem/2512

2512번: 예산

풀이

앞에서 설명한 "나무 자르기" 문제와 매우 비슷한 문제입니다.

예산의 상한액을 결정하면 가능/불가능으로 답이 나오기 때문에 파라메트릭 서치를 해주면 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int N, M;
ll X, ans, A[10010];

bool f(ll x) {
    ll sum=0;
    for(int i=1; i<=N; i++) sum+=min(A[i], x);
    return sum<=M;
}

void BinarySearch(int s, int e) {
    while(s<=e) {
        int mid=(s+e)/2;
        if(f(mid)) ans=mid, s=mid+1;
        else e=mid-1;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++) {
        cin>>A[i];
        X=max(X, A[i]);
    }
    cin>>M;
    BinarySearch(0, X);
    cout<<ans;
    return 0;
}

 

예시  3

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

풀이

랜선의 길이를 $x$로 정하면 가능 여부는 $\sum_{i=1}^{n} {\lfloor \frac {A_i} {x} \rfloor} \ge N$?로 결정되므로 랜선의 길이를 기준으로 파라메트릭 서치를 하면 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
int N;
ll K, X, ans, A[10010];

bool f(ll x) {
    ll sum=0;
    for(int i=1; i<=N; i++) sum+=A[i]/x;
    return sum>=K;
}

void BinarySearch(ll s, ll e) {
    while(s<=e) {
        ll mid=(s+e)/2;
        if(f(mid)) ans=mid, s=mid+1;
        else e=mid-1;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; i++) {
        cin>>A[i];
        X=max(X, A[i]);
    }
    BinarySearch(1, X);
    cout<<ans;
    return 0;
}