C언어 bsearch() - 이진탐색 함수

bsearch 라는 함수는 특정 배열안의 값을 찾고자 할 때, 이진 탐색의 방법으로 빠르게 찾아주는 함수입니다.

단, 이진탐색이라는 특징 상 배열은 반드시 정렬(sorting)되어 있어야 합니다.

* 이진탐색이란?

 - 가운데에서부터 탐색을 시작하며 오름차순으로 정렬되어 있는 배열의 경우, 찾는 값이 비교대상의 값보다 작으면 왼쪽에, 비교대상의 값보다 크면 오른쪽에 위치하게 됩니다. 

배열을 계속 반씩 잘라가며 탐색을 하며, 따라서 배열의 개수 n에 대하여 O(log n)의 속도로 탐색이 가능합니다. 배열의 개수가 많아질수록 더욱 효과적이게 됩니다.

아래는 이진탐색의 예제입니다. 1부터 100사이의 임의의 숫자 10개가 배열안에 정렬되어 있습니다.

86을 찾고자 할때, 이진 탐색의 경우 아래와 같이 이루어집니다.

1. 배열을 가운데로 잘라 47과 비교합니다.

10

15

21

31

47

51

59

72

86

95

2. 47 < 86 이므로, 오른쪽 배열의 절반의 값인 72와 비교합니다.

10

15

21

31

47

51

59

72

86

95

3. 72 < 86 이므로, 오른쪽 배열의 절반의 값인 86과 비교합니다.

10

15

21

31

47

51

59

72

86

95

4. 찾으려는 값과 86이 일치하므로 이진탐색이 종료됩니다.

자 이제 bsearch 함수를 보도록 하겠습니다.

bsearch 함수의 프로토타입은 다음과 같습니다.

int bsearch (const void *key,

              const void *base, 

              size_t nel, 

              size_t width,
              int (*compare)(const void *, const void *)

•  함수명    : bsearch
•  필요헤더 : stdlib.h
•  리턴타입 : int
•  파라미터 : 1. 찾을 값의 주소
                  2. 찾을 대상이 되는 배열
                  3. 배열의 총 엘리먼트 개수
                  4. 배열 한 개의 크기 (size)
                  5. 비교를 수행할 함수의 포인터
                     (compare 함수의 리턴값이 양수일 경우 오른쪽, 음수일 경우 왼쪽을 탐색)
•  리턴값    : key에 해당하는 값을 찾을 경우 : key가 위치한 주소 (배열의 주소)
                  값을 찾지 못했을 경우 : NULL
•  함수역할 : 이진탐색을 이용하여 값을 찾는다.

qsort()와 구조적으로 굉장히 비슷합니다.

주의하셔야할 점은 이 라이브러리를 사용하기 위해서는 반드시 배열이 오름차순으로 정렬되어 있어야 합니다.

(만일 내림차순으로 정렬된 배열을 사용하고 싶으시다면, compare함수를 반대로 만들어주시면 됩니다.)

그럼 바로 소스코드 예제를 한번 보도록 하겠습니다.

#include <stdio.h>
#include <stdlib.h>

int compare (void *first, void *second)
{
    if (*(int*)first > *(int*)second)
        return 1;
    else if (*(int*)first < *(int*)second)
        return -1;
    else 
        return 0;
}

int main(int argc, char** argv)
{
    int arr[] = {10,15,21,31,47,51,59,72,86,95};
    int arr_size = sizeof(arr) / sizeof(int);
    int key;
    int *find;

    key = 86;
    if ((find = bsearch(&key, arr, arr_size, sizeof(int), compare)) != NULL)
        printf("Find value: %d\n", *find);
    else
        printf("Can't Find\n");
    
    key = 92;
    if ((find = bsearch(&key, arr, arr_size, sizeof(int), compare)) != NULL)
        printf("Find value: %d\n", *find);
    else
        printf("Can't Find\n");

    return 0;
}

실행결과: