20-1-나.이분 검색

이분 검색은 구간의 중간값과 키값의 대소를 구분하여 테이블을 절반씩 나눠 가며 비교하는 방법이다. 순차 검색이 상등 비교만 하고 순서대로 검색하는데 비해 이분 검색은 대소 비교를 통해 구간을 나눠 비교하는 좀 더 지능적인 방법이라고 할 수 있다. 한 번 비교할 때마다 테이블의 길이가 절반씩 줄어 들기 때문에 검색 효율은 아주 좋으며 테이블이 웬만큼 커도 느려지지 않는다.

영한 사전에서 girl이라는 단어를 찾는다고 해 보자. 순차 검색은 사전의 처음부터 a, ab, aba, abc, ace 등등의 단어를 비교하면서 girl이 나올 때까지 찾는 비효율적인 방법이다. 이분 검색은 사전의 중간 부분을 펼쳐 girl보다 더 크면 앞쪽으로, 작으면 뒤쪽으로 가면서 점점 범위를 좁혀 가며 검색하는 방법이다. 일반적으로 사전을 검색할 때 우리는 이분 검색 방법을 사용하며 그래서 사전이 아무리 커도 단어를 찾는 속도가 빠르다.

이분 검색이 가능하려면 테이블의 모든 자료가 오름차순으로 영한 사전처럼 정렬되어 있어야 한다는 제약이 있다. 그래서 자료를 삽입할 때 항상 다음 검색을 위해 제 위치에 삽입해야 하는 관리상의 어려움이 있지만 그 대가로 빠른 검색 속도를 보장 받을 수 있다. 다음 예제는 오름차순으로 정렬되어 있는 정수 배열에서 중간쯤의 키값을 이분 검색으로 찾는다.

예 제 : BinarySearch

#include <Turboc.h>

int BinarySearch(int *ar,unsigned num,int key)

{

unsigned Upper,Lower,Mid;

Lower=0;

Upper=num-1;

for (;;) {

Mid=(Upper+Lower)/2;

if (ar[Mid]==key) return Mid;

if (ar[Mid]>key) {

Upper=Mid-1;

} else {

Lower=Mid+1;

}

if (Upper<=Lower) {

return -1;

}

}

}

void main()

{

int ar[]={2,6,13,19,21,21,23,29,35,48,62,89,90,95,99,102,109,208,629};

unsigned num;

int key,idx;

num=sizeof(ar)/sizeof(ar[0]);

key=29;

idx=BinarySearch(ar,num,key);

if (idx == -1) {

puts("찾는 값이 없습니다.");

} else {

printf("찾는 값은 %d번째에 있습니다.\n",idx);

}

}

ar 배열이 검색 대상 테이블이며 19개의 정수들이 크기순으로 잘 나열되어 있다. BinarySearch 함수는 이 배열에서 key를 찾는데 예제의 경우 29라는 수가 키 값으로 주어졌다. 이 함수가 ar에서 29를 찾는 과정은 다음과 같다.

최초 Lower가 배열의 처음, Upper가 배열의 끝을 가리키고 Mid는 이 둘의 중간인 ar[9]를 가리키고 있다. 이 상태에서 ar[9]의 값 48과 찾고 있는 키값 29를 비교해 보니 48이 훨씬 더 크다. 그러므로 찾는 값이 48보다 더 아래쪽에 있을리가 만무하며 Upper가 48의 바로 위인 ar[8]로 이동함으로써 검색 범위가 절반으로 줄어든다. 키값이 ar[9]보다 더 작으므로 ar[9]도 검색 대상에서 제외됨을 유의하도록 하자. Upper가 Mid로 가는 것이 아니라 Mid-1로 가는데 이렇게 하지 않으면 검색 범위를 빨리 좁힐 수 없음은 물론이고 키와 일치하는 값이 없을 때 무한 루프에 빠질 수도 있다.

다음 루프를 돌 때 Mid는 새로운 Lower와 Upper의 중간 지점인 ar[4]로 이동하며 이 상태에서 ar[4]의 값 21과 키값 29를 비교해 보니 키가 더 크다. 이 경우에는 ar[4]이전에는 찾는 키가 없다는 것을 알 수 있으며 Lower가 ar[5]로 이동한다. 이런 식으로 계속 절반씩 검색 범위를 줄여 나가다 보면 언젠가는 Mid 위치에서 키값을 찾을 수 있다. 만약 찾는 키가 배열에 없다면 Lower와 Upper가 같아지거나 아니면 Lower가 더 커지는 상태가 되는데 이때는 찾지 못했다는 -1을 리턴하면 된다.

이분 검색은 범위를 계속 절반씩 줄어 가면서 검색하기 때문에 테이블이 커도 비교 회수가 많지 않은 것이 장점이다. 배열 크기가 n일 때 최악의 경우라도 log₂n번 비교하면 원하는 값을 찾을 수 있다. 극단적인 경우 n이 40억이라 하더라도 기껏 32번만 비교하면 되므로 순차 검색과는 비교할 바가 아니다. 이분 검색이 이렇게 속도가 빠른 이유는 자료가 크기순으로 정렬되어 있기 때문이다.

그래서 이분 검색에 사용할 자료는 삽입할 때도 반드시 이 조건을 지키도록 주의해야 한다. 만약 중간에 정렬되지 않은 자료가 있다면 대소 비교 연산문의 결과를 신뢰할 수 없으므로 이분 검색 알고리즘은 제대로 동작하지 않는다. 정렬되어 있지 않다면 정렬한 후 이분 검색을 하든지 아니면 처음부터 정렬 상태를 유지하도록 자료를 관리해야 하는 부담이 있다. 다행히 원래부터 정렬되어 있는 자료도 많이 있는데 이런 자료에 대해서는 바로 이분 검색 알고리즘을 쓸 수 있다.

또한 처음부터 순서대로 검색하는 것이 아니라 중간 부분을 쿡쿡 찔러보는 식이므로 키값이 중복될 경우 어떤 키가 검색될지 알 수 없는 맹점이 있다. 위 예에서 키를 21로 바꿀 경우 두 개의 21중 어떤 값이 검색될 것인가를 예측할 수 없으며 테이블 크기가 가변적일 때는 상황에 따라 검색되는 값이 달라진다. 키의 중복을 해결하든지 아니면 이분 검색으로 일단 찾은 후 아래 위의 레코드를 순차 검색하여 중복된 값 중 하나를 선택해야 한다.

이분 검색은 복잡성에 비해 효율이 굉장히 좋기 때문에 검색 알고리즘 중에는 가장 실용적이고 자주 사용된다. 그래서 C 표준은 라이브러리 차원에서 이분 검색 함수를 제공하는데 바로 다음 함수이다. 이 함수는 임의의 타입에 대해서도 사용할 수 있다.

void *bsearch( const void *key, const void *base, size_t num, size_t width, int ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );

key는 찾고자 하는 값이고 base는 배열 선두 번지, num은 요소 개수, width는 요소의 크기이다. 그리고 compare는 사용자가 지정하는 비교 함수인데 비교 대상이 되는 두 개의 값을 전달한다. compare 함수는 이 두 값을 비교해 보고 첫 번째 인수가 더 작으면 음수, 같으면 0, 더 크면 양수를 리턴해야 한다. 임의의 타입에 대해 사용하기 위해 void *를 사용하며 타입별로 비교하는 방법이 다양하므로 비교 함수를 따로 전달한다는 점이 조금 복잡하지만 사용하기는 굉장히 쉬운 편이다. 앞의 예제를 bsearch 함수로 다시 작성해 보자.

예 제 : bsearch

#include <Turboc.h>

int compare(const void *elem1,const void *elem2)

{

return (*(int *)elem1 - *(int *)elem2);

}

void main()

{

int ar[]={2,6,13,19,21,21,23,29,35,48,62,89,90,95,99,102,109,208,629};

unsigned num;

int key;

int *ptr;

num=sizeof(ar)/sizeof(ar[0]);

key=29;

ptr=(int *)bsearch(&key,ar,num,sizeof(int),compare);

if (ptr==NULL) {

puts("찾는 값이 없습니다.");

} else {

printf("찾는 값은 %d번째에 있습니다.\n",ptr-ar);

}

}

이분 검색 알고리즘 구현은 bsearch 함수 내부에서 하며 사용자는 이 함수가 전달하는 값을 비교해서 그 결과만 리턴하면 된다. compare 함수는 두 정수의 대소 관계를 비교해야 하므로 단순히 두 값의 차를 리턴하면 된다. 만약 검색 대상이 문자열이라면 strcmp(i) 함수로 비교한 값을 리턴하면 된다. 결과는 앞의 예제와 동일하되 bsearch 함수는 어셈블리로 작성되어 있고 고도로 최적화되어 있으므로 훨씬 더 빠르고 안정적이다.

좀 더 발전된 이분 검색 방법으로 피보나치 수열을 사용하거나 보간을 하는 방법이 있다. 이 방법들은 범위를 줄일 때 키가 없다고 판단되는 부분을 빠르게 건너뜀으로써 단순 이분 검색에 비해서는 속도가 조금 더 빠르다. 그러나 알고리즘이 다소 복잡하고 속도차도 많이 나는 편은 아니므로 이분 검색이 필요할 때는 표준 bsearch 함수 정도면 대체로 충분하다.

이분 검색은 중간 부분을 빠르게 액세스할 수 있어야 하므로 배열에 대해서만 사용할 수 있다. 연결 리스트는 목록상의 임의 노드로 바로 이동하는 능력이 없기 때문에 아무리 정렬되어 있더라도 이분 검색을 사용할 수 없다. 연결 리스트는 순차적으로만 값을 읽을 수 있으므로 오로지 순차 검색만 가능한 자료 구조이다.