bsearch 이진 검색 함수

bsearch 이진 검색 함수

이번에는 이진 검색 함수 bsearch에 대해서 알아볼것이다.

bsearch 함수를 사용하려면 stdlib.h 파일은 include 해줘야 한다.

이진 검색이란?? 방대한 크기의 배열을 빠르게 검색할 수 있다. 검색의 효율은 오름차순으로 정렬된 배열에 의해서 결정이 된다.

검색이 수행되는 과정은 다음과 같다.

1. 검색 키(key)가 배열의 중앙에 있는 요소와 비교한다.

2개의 값이 일치한다면 검색이 수행되고, 그렇지 않다면 검색 키는 배열의 요소보다 작거나 큰 경우이다.

2. 검색 키가 배열의 요소보다 작다면 일치하는 내용은 배열의 앞 부분에 위치되어 있을 것이다.

검색 키가 배열의 요소보다 크다면 일치하는 요소는 배열의 뒷부분에 위치되어 있을 것이다.

3. 검색은 배열의 절반을 범위로 하게 되고 알고리즘은 1단계로 돌아간다.

이진 검색을 사용하려면 반드시 오름차순으로 정렬이 되어 있어야 한다.

bsearch 함수의 원형을 한번 보자.

void *bsearch(const void *key, const void *base, size_t num, size_t width, int(__cdecl *compare)(const void *eleml, const void *elem2));

▶ key = 검색할 키 값

▶ base = 검색할 배열의 번지

▶ num = 총 배열 요소의 갯수

▶ width = 배열 요소가 차지하는 크기, int형은 4바이트 double형은 8바이트

▶ compare = 비교 함수, 정수값 및 문자열을 모두 비교하는 함수를 사용 가능하다.

#include <stdio.h>
#include <stdlib.h>
int intcmp(const void *v1, const void *v2);
main()
{
    int key = 5, *ptr;
    int array[10] = { 150, 27, 33, 1, 5, 100, 99, 75, 81, 10 };
 
    qsort(array, 10, sizeof(array[0]), intcmp);
    ptr = bsearch(&key, array, 10, sizeof(array[0]), intcmp);
 
    if (ptr) puts("5를 찾았습니다.");
}
int intcmp(const void *v1, const void *v2) { return (*(int*)v1 - *(int*)v2); }

< 출력 >

9행에서 qsort 함수를 사용해 오름차순으로 정렬을 해준다.

10행에서 key 값을 검색을 한다. 만약 검색되지 않았다면 NULL을 반환한다. 검색이 되었다면 위치에 대한 번지 값을 반환한다.

12행에서 key 값이 검색 되었으면 화면에 뿌려준다.

바이너리 검색(이진 검색)은 매우 효율적이다.

2018/07/18 - [프로그래밍/C] - qsort(퀵 정렬) 정렬하기