[알고리즘] 바이너리 서치 구현과 설명

 정렬과 더블어 따라오는 탐색 중 바이너리 서치에 대하여 설명하고, 이를 구현한 코드를 포스팅한다.

 

탐색은 요구에 맞는 데이터를 찾는 과정으로, 실무나 프로젝트 또는 알고리즘 문제를 풀어본 사람들은 잘 알겠지만 가장 빈번하게 일어난다. 따라서 이러한 탐색에 필요한 시간 복잡도를 줄이므로써, 더욱 효율적인 프로그램을 작성할 수 있게 한다.

 

일반적으로 전체 탐색을 통하여 검색을 하는 경우 N개의 데이터에 대하여 O(N)의 시간 복잡도를 가진다. 하지만 정렬된 데이터에 대하여 키에 대한 값을 탐색하는 경우, 이를 O(lgN)으로 줄일 수 있으며, 사실상 lgN은 상수에 근접하므로 O(N) 탐색에 비하여 더욱 효율적이고 같은 시간내 다양한 작업을 할 수 있다.

 

바이너리 서치는 정렬된 데이터에서 탐색하는 크기를 반으로 줄여가면서, 원하는 데이터를 찾아가는 방법이다. 만약 오름차순으로 정렬된 1~100까지의 자연수 배열이 있다고 하자. 이때 배열의 중간의 값을 뽑으면 50이며 만약 찾는 값이 50보다 적다면 1~49까지에 대하여 다시금 이 작업을 반복하는 것이다.

이렇게 되면 우리는 100->50->25->12->6->3->1 (계산은 대충 알아보자.)의 과정을 통하여 총 6번만에 원하는 값의 위치를 찾아 낼 수 있다.

 

 

그러면 이런 바이너리 서치를 어떻게 구현해야 할까?

 

(1) 정의하기

배열 : 0 ~ n-1 (길이 n)

찾고자 하는 값 : a[i-1] < X <= a[i]인 i

오름차순으로 정렬되있다고 가정

(2) 코드로 구현

#include <iostream>
using namespace std;

int h[6] = { 0, 3, 5, 7, 9 };
int n = 5;

int binary(int x){
	int lo = -1;
    int hi = n;
    
    while(lo+1 < hi){
    	int mid = (lo + hi)/2;
        if(h[mid] < x)
        	lo = mid;
        else
        	hi = mid;
    
    }
    return hi;
}

int main(){
	printf("%d\n", binary(-1));
	printf("%d\n", binary(2));
	printf("%d\n", binary(5));
	printf("%d\n", binary(9));
	printf("%d\n", binary(10));

}

 일단 a[i-1] < X <= a[i]으로 가정했고, 우리는 루프가 끝날 때 반드시 lo=i-1, hi = i가 되도록 해야한다. 따라서 lo+1<hi으로 조건을 주어 lo+1>=hi가 되며, 앞서 언급한 조건에 따라 lo < hi이므로, 두 조건을 합치면 lo+1 = hi가 된다.

 또한 h[mid]가 x보다 작은 경우는 lo ~ mid 까지 탐색할 필요가 없으므로 lo = mid를 주며, 그 반대의 경우도 마찬가지다. 여기서 mid +1을 주어도 무방하지만 어차피 1씩 차이나는 것은 시간 복잡도에 크게 영향을 주지 않으므로 외우기 편하게 저렇게 짜면 된다.

 binary라는 함수는 존재하는 경우 해당 인덱스를 아닌 경우는 같거나 큰값의 인덱스를 반환한다. 물론 값이 없을 경우 잘못된 인덱스를 던질 수 있다. 따라서 반드시 리턴되는 인덱스가 무엇을 가르키는지 확인하여 존재 여부를 확인해야 한다.

 

물론 C++의 binary_search를 쓰면 쉽지만 이해하는 것이 중요