이진 탐색
2022/11/15(화요일)
정렬된 배열에서의 탐색
정렬되어 있지 않은 배열의 순차 탐색을 이해하고 구현하기는 쉽다.
만약 배열의 항목이 얼마 되지 않는 경우에는 충분히 가능한 알고리즘이다.
그러나 배열이 많은 항목을 가지는 경우에는 순차 탐색은 너무나 비효율적인 방법이다. 예를 들어 10개중의 하나를 찾는 것은 순차 탐색으로 가능하지만 100000개 정도라면 상당한 시간이 소요된다. 만약 10억 개 중에서 하를 찾는 문제라면 순차 탐색하는 것은 상당히 비효율적이다. 따라서 보다 빠른 방법이 요구된다. 아주 효율적인 탐색 알고리즘인 이진 탐색을 살펴보겠다.
이진 탐색
정렬된 배열의 탐색에는 이진 탐색이 가장 적합하다. 이진 탐색은 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 도는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.
이러한 방법에 의해 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄인다.
위의 그림에서 (a)는 정렬된 배열에서 숫자 5를 찾는 과정을 나타낸 것이다. 먼저 배열의 중간에 있는 값인 7과 비교된다. 5가 중간에 있는 값인 7보다 작으므로 5는 앞부분에 있을 것이다. 따라서 이제부터 뒷부분은 고려대상에서 제외된다. 다시 남아있는 앞부분의 중간에 있는 값인 3과 5가 비교된다. 5가 3보다 크므로 이번에 앞부분이 제외되고 뒷부분만이 남는다. 다시 뒷부분의 중간값인 5와 우리가 찾고 있는 값인 5를 비교하면 일치한다. 따라서 탐색은 성공한다. 탐색이 실패하는 예를 (b)에서 보였다. 배열에 있지 않은 2를 탐색하여 보면 중간값과 계속 비교하다가 더이상 비교할 항목이 남아 있지 않게 되고 결국 탐색은 실패한다.
반복을 이용한 이진 탐색
int search_binary2(int key, int low, int high) {
int middle;
while( low <= high ) {
middle = (low+high)/2;
if( key == list[middle] )
return middle;
else if( key > list[middle] )
low = middle+1;
else high = middle-1;
}
return -1; // 탐색 실패
} // 반복을 이용한 이진 탐색
순환 호출을 이용한 이진 탐색
int search_binary(int key, int low, int high) { // 순환 호출을 이용한 이진 탐색
int middle;
while( low <= high ) { // 아직 숫자들이 남아 있으면
middle = (low+high)/2;
if( key == list[middle] )
return middle; // 탐색 성공
else if( key > list[middle] )
returnsearch_binary(key,low,middle-1); //왼쪽부분리스트탐색
else return search_binary(key, middle +1, high); // 오른쪽 부분 리스트 탐색
}
return -1; // 탐색 실패
}
순환 호출로 구현하기 위하여 위의 알고리즘의 매개변수를 low와 high로 해야한다. 즉 어떤 시점에서 탐색되어야할 범위는 low에서 high까지가 된다. 맨 처음에는 low가 0, high가 n - 1이 될 것이다. 그리고 순환 호출에는 항상 순환 호출을 끝내기 위한 코드가 들어가야 한다. 만약 이러한 코드가 없다면 무한히 호출이 이루어질 것이다. 이 문제에서는 탐색 범위가 1보다 작다면 즉 탐색해야 될 항목이 없는 경우에는 순환 호출을 하지 않으면 된다.