(2) 2진 탐색

(2) 2진 탐색

순차 탐색은 가장 이해하기 쉬운 탐색의 방법임에는 틀림없다. 그러나 동시에 가장 느린 탐색
방법임에도 틀림없다. 그러면 보다 빠른 탐색 방법에는 어떤 것이 있을까?

이 얘기를 하기 전에 강좌1에서 얘기한 명함의 경우를 다시 생각해 보자. 명함을 찾을 때에 실제
로 앞에서 얘기한 순차탐색의 방법으로 찾는 사람이 있을까? 만일 명함이 '가나다'순으로 정리되
어 있지 않다면 모르지만 정리 되어 있다면 적당한 위치를 짚어서 살펴 보고, 다시 적당한 위치를
살펴보는 방법을 택할 것이다.

결국 순차적으로 정리되어 있는 자료에 대해서 항상 중간값과 비교해서 어느 쪽에 존재하는가를
판정하는 식의 방법을 사용하는 것을 2진 탐색이라고 한다.

이 방법을 사용하면 자료의 개수가 많아짐에 따라서 순차탐색에 비해 사용되는 시간이 현저하게
절약된다.

이 방법은 앞의 순차 탐색에 비해 다소 복잡해지는 면이 있으나, 그다지 어렵지는 않다. 구현 방
법으로는 원하는 값이 존재할 것으로 보이는 영역의 왼쪽 위치와 오른쪽 위치를 중간값과 원하는
값의 비교결과에 따라 변화 시킴으로써 이루어진다. (그림3 참조) 아래의 예는 오름차순으로 정
리된 자료에 대한 2진 탐색 구현의 예이다.(순차탐색과 같은 가정하에서)

(리스트3) 2진 탐색 알고리즘
int Binary_Search(int key,int a,int last_item)
{
int left_item,right_item;
int mid_item;

       left_item=0;
        right_item=last_item;
        while (left_item<right_item)
        {
                mid_item=(left_item+right_item)/2;
                if (a[mid_item]<key)
                        left_item=mid_item;
                else
                        right_item=mid_item;
        }
        if (a[left_item]==key)
                return left_item;
        else
                return NOT_EXIST;
}

위의 예에 대해 간단히 설명을 덧붙이자면, 주어진 while 루핑을 빠져 나오는 경우는 left_item
의 값이 right_item 값이나 mid_item의 값과 같아질 경우이다. 따라서, 그 아래에 나오는 if 문
에서는 어느 값을 사용하여 비교하여도 상관없지만, mid_item 값을 사용하면 문제가 발생할 수
있다. 즉, last_item이 0이어서 루핑을 거치지 않는 경우에는 mid_item 값이 설정되어 있지 않으
므로 주의해야 한다.