<알고리즘> 이분 탐색 (Binary Search, 바이너리 서치)

이분 탐색 이란?

오름차순으로 정렬되어 있는 배열에서 특정한 값을 찾을 때에 사용가능한 알고리즘이다. 순차적으로 특정한 값을 찾는 것 보다 빠른 시간내에 찾을 수 있다는 장점이 있다. 순차적으로 찾을 때에는 시간 복잡도가 O(N)이지만 이분탐색을 이용하는 경우 시간복잡도는 O(logN)이다. 따라서 오름차순으로 정렬되어 있는 배열에서의 탐색은 이분 탐색이 효과적이다.

간단히 설명하면 방법은 배열의 중간 값과 비교를 하여서 해당 값보다 크다면 중간값 이후의 배열에서 찾는 값이 나올때 까지 반복하고 작은 경우에는 중간값 이전의 배열에서 찾는 값이 나올때 까지 반복한다. 자세한 설명은 아래 그림과 같다.

 

이분 탐색 예시 그림

 

위와 같이 중간값과 목표 값을 계속 비교하며 탐색 범위를 재설정한다. 이를 통해서 순차 탐색 보다 빠른 시간내에 탐색이 가능하다. 만약 mid와 target이 같다면 탐색을 종료하며 그때의 값이 목표한 값이다. 만약 목표한 값을 찾지 못하였는데 end의 값이 start보다 작아지게 된다면 해당 목표 값은 배열에 존재하지 않는다는 뜻이 된다.

 

🔎 정렬되어 있는 배열에서만 사용 가능하다.

 

---

이분 탐색 예시 코드

void binary_search(){
    int a[101];

    for (int i = 1; i < 101; i++){
        a[i] = i;
    }
    
    int target;
    
    cin >> target;
    
    int start = 1, end = 100;
    
    while(start <= end){
        int mid = (start + end) / 2;
        
        if (mid == target){
            cout << "Search" << endl;
            break;
        } else if (mid > target){
            end = mid - 1;
        } else {
        	start = mid + 1;
        }
    }
}

 

반복문을 통해서 target의 값을 찾을때까지 탐색 범위를 재설정한다. mid 값과 비교하여서 빠른 탐색이 가능하게 한다.

 

---

 

파라메트릭 서치 (Parametric Search)

파라메트릭 서치란, 이분 탐색을 이용하여 문제를 풀 수 있는 최적화 문제들을 의미한다. 어떤 조건들을 만족하는 범위 내에서 가장 최대값 혹은 최솟값을 구하는 문제에서 이분 탐색을 활용하여서 문제를 해결할 수 있다. 

예를 들면 조건1, 2, 3이라는 각각의 조건들을 만족하면서 최대인 숫자를 찾을때 이분 탐색을 활용하면 주어진 범위내에서 어떤 값 X가 위 조건들을 만족한다면 그보다 큰 범위에서 다시 찾아보고 또 다른값 Y는  해당 조건들을 만족하지 않는다면 그보다 작은 범위에서 다시 찾아본다. 이를 통해서 최대 X값을 찾을 수 있다. 만약 순차적으로 찾는다면 최대값을 찾기에 오랜 시간이 걸리지만 이분탐색을 활용한다면 그렇지 않다.

 

백준 1654번 문제를 예로 들수 있다.

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

1654번: 랜선 자르기

 

위 문제의 답을 파라메트릭 서치를 이용해 구한 코드는 아래와 같다.

 

#include <bits/stdc++.h>

using namespace std;

unsigned int ans;
int k, n;
unsigned int a[10005];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> k;
    cin >> n;

    unsigned int maxi = 0;
    
	for (int i = 0; i < k; i++)
	{
		cin >> a[i];
		maxi = max(maxi, a[i]);
	}

    unsigned int st = 1, ed = maxi, mid;

    while (st <= ed)
    {
        mid = (st + ed) / 2;

        unsigned int now = 0;

        for (int i = 0; i < k; i++){
            now += a[i] / mid;
        }

        if (now >= n){
            st = mid + 1;
            ans = max(ans, mid);
        } else {
            ed = mid - 1;
        }
    }
    
    cout << ans;
}

 

감사합니다!

 

참고:

https://velog.io/@lake/이분탐색-파라메트릭-서치Parametric-Search

[이분탐색] 파라메트릭 서치(Parametric Search)

https://code-angie.tistory.com/3

[알고리즘 / Python] 이분 탐색 / 이진 탐색 (Binary Search)