bsearch() 함수 설명 및 알고리즘

#include <stdlib.h>

void *bsearch( const void *key,

               const void *base,

               size_t nmemb,

               size_t size,

               int (*compar)(const void *, const void *));

 

Parameters :

key    : 찾고자 하는 키 값(Target)

base   : 찾을 대상이 있는 Array Object의 주소

nmemb  : array element 개수

size   : array element 하나의 byte size

compar : 비교함수. 각각 두 개의 파라미터는 key와 하나의 array element를 가리키는 주소값이다.

         자세한 내용은 Description 참조.

 

Return Value :

함수 실행 결과, 매칭하는 Array Object의 주소값을 리턴한다.

매칭되는 결과값이 없는 경우는 NULL을 리턴한다.

 

Description :

bsearch()함수는 binary search를 수행한다.

물론 직접 binary search 알고리즘을 구현할 수도 있겠지만 구태여 그렇게 힘들일 필요 없다.

다 만들어서 제공해주고 있으니 만들어준 사람 성의를 생각해서 그냥 잘 가져다 쓰면 된다!

 

※ 비교함수(compar)

   key 파라미터와 array element를 비교하여 key 값이 더 작으면 음수, 같으면 0, 더 크면 양수를 리턴한다.

   실제 프로그래밍시 비교함수는 직접 코딩해줘야한다.

   <비교함수 코딩 예>

   static int compare(const void *key, const void *data) {
     return *(int *)key - *(int *)data;
   }

   위의 비교함수를 이용하여 bsearch()함수를 호출할 때는 이렇게 하면 된다.

   int *d = (int *d)bsearch(&key, data, sizeof data / sizeof(int), sizeof(int), compare);

 

bsearch 알고리즘:

 

lsearch()나 lfind()가 테이블의 첫번째 요소부터 마직막 요소까지 하나씩 데이터를 검색한다면 bsearch()는 이진 검색으로 매우 빠르게 자료를 검색할 수 있습니다.

그러나 이진 검색을 하기 위해서는 반드시 테이블의 자료는 정령되어 있어야 합니다. 왜 이진 검생르 위해 테이블이 정렬되어 있어야 하는지 이유를 보겠습니다.

지금 테이블에 1에서 10까지 데이터가 차례로 정렬되어 있습니다.

1

21

32

43

54

65

76

87

98

190

이 테이블에서 98을 찾아 보겠습니다. 우선 전체 테입블 요소 중 가운데에 해당하는 다섯번째 데이터와 비교합니다.

1

21

32

43

54

65

76

87

98

190

가운데 요소와 비교했더닌 검색하려는 데이터 98보다 작습니다. 그러므로 1부터 43까지는 검색할 필요가 없습니다.

이번에는 5 번째 요소와 10번째 요소의 가운데 요소인 8번째 요소와 비교합니다.

1

21

32

43

54

65

76

87

98

190

역시 찾으려는 98보다 작습니다. 이번에는 8 번째와 10 번째의 가운데에 해당하는 9 번째와 비교하게 됩니다.

1

21

32

43

54

65

76

87

98

190

lsearch()와 lfind()는 첫번째 요소부터 차례로 검색하기 때문에 9번이나 비교해야 하지만 bsearch 는 이와 같이 정렬된 자료에서 이분화해서 검색하므로 단 3번의 비교로 자료를 검색할 수 있습니다.

그러므로 매우 많은 자료에서는 이진 검색인 bsearch()가 매우 빠르게 검색할 수 있습니다.

 

[출처] bsearch() 함수 설명 및 알고리즘|작성자 kernel