0x04.탐색 알고리즘(2):이진 탐색

2. 이진 탐색

선형탐색과 마찬가지로 이진탐색에서도 배열에 레코드를 삽입하는 방법을 사용하지만, 요소 값의 크기 순으로 삽입한다는 점이 다르다. 다시 말해, 배열의 데이터가 크기순으로 정렬된다.

(아래의 배열은 데이터 값이 작은 것부터 순차대로 정렬되도록 하였다)

위 배열에서는 low에서 high까지의 요소들이 탐색 대상이 되는데, low와 high라는 변수로 범위를 지정함으로써 탐색 범위를 제한할 수 있다.

젤 먼저 low와 high사이에 위치한 정중앙 데이터값인 mid와 찾으려는 데이터의 값을 비교한다. 찾는 값이 mid보다 작다면 mid 이후의 요소들은 탐색하지 않아도 되고, 반대로 mid보다 값이 크다면 mid 이전 요소들은 탐색할 필요가 없기 때문이다.

이진탐색에서는 다음의 두 알고리즘이 사용된다.

① 탐색 알고리즘

② 삽입 알고리즘

① 탐색 알고리즘

void search(keytype target, boolean * found, index * pos){

   index high, mid, low;

   low=1;

   high=n;

   while(low<=high){

       mid=(low+high)/2;

       if(target<=table[mid].key) high=mid-1;

       if(target>=table[mid].key) low=mid+1;

   }

   *found=(low=high+2) ? true:false;

   *pos=low-1;

}

변수부터 설명을 하자면 target은 비교하기 위한 대상이고, pos는 탐색이 성공한 경우에는 찾고자하는 데이터의 위치를, 찾지 못한 경우에는 target보다 작은 최댓값의 위치를 가진다.

if(target<=table[mid].key) high=mid-1; 구문은 다음을 수행한다.

mid값보다 target값이 작거나 같으면 high의 값이 mid-1이 되어서 mid와 high 사이의 범위를 조건에서 제외시켜 효율적으로 탐색할 수 있다.

if(target>=table[mid].key) low=mid+1;   의 실행결과는 아래와 같이 low의 값을 변경시켜 위의 조건식과 반대로 low와 mid사이 범위를 탐색에서 제외시킨다.

target의 값이 찾는 데이터의 값과 같은 경우에는 위의 두 조건식이 동시 충족되기에, 다음과 같이 수행된다.

high의 값이 mid-1이 되고, low의 값이 mid+1이 되면서 mid값이 탐색결과가 된다.

결국, 위와 같이 탐색에 성공하면 low=high+2가 되기 때문에 조건문을 빠져나올 수 있다.

반대로 탐색에 실패하는 경우에는 마지막 수행결과가 다음의 두 형태중 하나일 것이다.

⒜ low=mid+1 (target값이 mid보다 크거나 같은 경우)

⒝ high=mid-1 (target값이 mid보다 작거나 잩은 경우)

전자의 경우 mid<=high이기 때문에 low=mid+1<=high+1이 성립한다. 따라서 low>high이면, low=high+1이 된다. 

후자의 경우에도 마찬가지이므로 전자와 같이 결국 low=high+1이 된다. 그러므로 pos의 값으로 low-1이 들어가게 되는 것이다.

이 알고리즘의 핵심은 탐색 성공시, low=high+2를, 실패시 low=high+1의 값을 가지게 된다는 것임!!

위의 알고리즘은 루프를 반복할 때마다 두 번의 조건식을 수행해야 하는 단점이 있기에, 아래와 같이 하나의 조건식으로 알고리즘을 작성할 수도 있다.

void search(keytype target, boolean * found, index * pos){

   index high, mid, low;

   low=1;

   high=n;

   while(low<=high){

       mid=(low+high)/2;

       if(target<table[mid].key) high=mid-1;

       else low=mid+1;

   }

   *pos=high;

   if(high==0) *found=false;

   else *found=(target==table[high].key);

② 삽입 알고리즘

첫부분에서 언급하였듯이 이진탐색은 데이터를 정렬된 상태로 저장하는 특징이 있다. 즉, 저장될 데이터는 high와 low사이에 삽입되어야 한다.

void insert(keytype x, othertype y, index *pos){

   index i;

   if(n>=SIZE) exit(1);  //배열과 크기 비교

   for(i=n, i>*pos+1; i--)

      table[i+1]=table[i];

   table[*pos+1].key=x;

   table[*pos+1].otherinfo=y;

   n=n+1;

}

for문을 통해 아래의 그림과 같이 삽입할 공간확보를 위해 맨 뒷부분부터 삽입지점까지 차례대로 뒤로 이동시킨다.

이진탐색은 선형탐색보다 탐색속도가 빠르다는 장점이 있지만, 삽입이 느리다는 단점이 있기에 탐색횟수가 많은 경우에 사용하는 것은 적합하지 않다는 것을 기억하도록 하자!