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)
]$
'컴퓨터 > 프로그래밍' 카테고리의 다른 글
C언어 이진트리 검색 및 추가 함수 tsearch() (0) | 2020.03.14 |
---|---|
C언어 테이블에서 테이터 검색 함수 lfind() (0) | 2020.03.14 |
C언어 테이블에서 테이터 검색 및 추가 함수 lsearch() (0) | 2020.03.13 |