본문으로 바로가기
homeimage
  1. Home
  2. 컴퓨터/프로그래밍
  3. C언 이진 검색 함수 bsearch()

C언 이진 검색 함수 bsearch()

· 댓글개 · 바다야크

C함수 이진 검색 bsearch()

C언어 함수 bsearch()는 자료를 이진 검색합니다.

  • 헤더: stdlib.h
  • 형태: void *bsearch(const void *key, const void *base, size_t nel, size_t width,
    int (*compar)(const void *, const void *))
  • 인수: const void *key 찾으려는 자료의 포인터 주소
    void *base 찾는 대상이 되는 테이블 포인터 주소
    size_t *nel table의 요소 개수
    size_t width 한 개 요소의 크기
    int (*compar)(const void *, const void *) 두 요소를 비교하기 위한 함수 포인터
  • 반환: void *찾은 데이터 요소의 포인터 주소, 만일 찾지 못했다면 NULL을 반환

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

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

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

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

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

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

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

C언어 bsearch() 함수 예제

#include &lst;stdio .h>
#include <stdlib .h>
#include <string .h>

int compare( const void *cmp1, const void *cmp2)
{
   return strcmp( (char *)cmp1, (char *)cmp2);
}

#define  SIZE_TABLE     10
#define  SIZE_ITEM      20

int main( void)
{
   char  table[SIZE_TABLE][SIZE_ITEM]  = { "com", "embedded",
                "falinux", "forum", "jwmx", "linux"};
   char *ptr;

   ptr   = (char *)bsearch( "forum", table, SIZE_TABLE, SIZE_ITEM, compare);
   printf( "찾아진 문자열= %sn", ptr);

   ptr   = (char *)bsearch( "embedded", table, SIZE_TABLE, SIZE_ITEM, compare);
   printf( "찾아진 문자열= %sn", ptr);

   ptr   = (char *)bsearch( "jwjw", table, SIZE_TABLE, SIZE_ITEM, compare);
   printf( "찾아진 문자열= %sn", ptr);
   
   return 0;
}

C언어 bsearch() 예제 실행 결과

]$ ./a.out
찾아진 문자열= forum
찾아진 문자열= embedded
찾아진 문자열= (null)
]$
SNS 공유하기
💬 댓글 개
최근글
이모티콘창 닫기
울음
안녕
감사해요
당황
피폐

이모티콘을 클릭하면 댓글창에 입력됩니다.