[집합과 검색] #4. bsearch 함수를 이용한 이진검색

유틸리티 함수: C언어의 표준 라이브러리는 다양한 요소의 자료형을 가진 배열에서도 검색 가능한 bsearch 함수를 제공한다.

 

	bseach
헤더	#include<stdlib.h>
형식	void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void*));
해설	입력 매개 변수 리스트 key 검색할 키 base 정렬 상태의 메모리 주소 nmemb 원소 개수 compare 비교 논리 bsearch 함수는 정렬 상태의 배열에서 이진 탐색으로 빠른 검색 기능을 제공한다. 마지막 인자는 두 개의 원소를 비교할 수 있는 알고리즘을 전달받습니다.따라서 bsearch 함수를 사용하려면 비교하는 함수는 사용하는 곳에서 정의하여 전달해야 합니다.비교하는 함수는 앞쪽이 클 때 양수, 같을 때 0, 뒤쪽이 클 때 음수를 반환하게 정의합니다. 출처: https://ehclub.co.kr/833 [언제나 휴일]
반환값	검사하는 대상(배열) 중에 일치하는 요소에 대한 포인터를 반환한다. 일치하는 요소가 없다면 NULL을 반환한다. 두 요소의 값이 같을 때 어느 요소와 일치하는지는 규정되있지않다.

 

맨 처음 요소를 가리키는 arr의 요소 개수가 num이고, 요소 크기가 size(==num)인 객체의 배열에서 key가 가리키는 객체와 일치하는 요소를 검색한다.

compar가 가리키는 비교 함수는 key 객체에 대한 포인터(변수 key의 위치)를 첫 번째 인수로, 배열 요소에 대한 포인터(배열의 위치)를 두 번째 인수로 하여 호출한다.

compar가 가리키는 비교 함수는 key 객체가 배열 요소보다 작으면 작은 값을, 일치하면 0을 크면 큰 값을 반환하도록 작성해야 함.
compar이 가리키는 배열은 key 객체와 비교가 가능한 작은 요소, 같은 요소, 큰 요소의 세 부분으로 이루어지며 이 순서대로 존재해야 한다.

 

/*변수와 함수의 인자*/

int num,key;
//num: 요소 개수
//key: 검색할 값

int *arr = (int*)malloc(sizeof(int)*num);
//동적할당한 배열

//bsearch함수의 사용
bsearch(&key,
    arr,
    num,
    sizeof(int),
    (int(*)(const void *,const void *))int_cmp
);

강력한 기능의 함수인만큼 사용 방법도 어렵고 인수도 5개가 필요하다는 단점이 있다.

bseach 함수를 이용한 검색

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

int int_cmp(const int *a, const int *b){
    if(*a<*b) return -1;
    else if(*a > *b) return 1;
    else return 0;
}

int main() {
    int num,key;
    puts("bseach 함수를 사용하여 검색 ");
    printf("요소 개수: ");scanf("%d",&num);

    int *arr = (int*)malloc(sizeof(int)*num);

    printf("오름차순으로 입력하세요.\n");
    for(int i=0;i<num;i++){printf("x[%d]: ",i);scanf("%d",&arr[i]);}

    printf("검색값을 입력하세요: ");scanf("%d",&key);

    int *rst = bsearch(&key,
                        arr,
                        num,
                        sizeof(int),
                        (int(*)(const void *,const void *))int_cmp
                    );

    if(rst == NULL) puts("검색에 실패하였습니다.");
    else printf("%d는 x[%d]에 있습니다.\n",key,(int)(rst-arr));
}

비교 함수

이진 검색의 검색 과정에는 검색하는 키 값과 요솟값을 비교하여 대소 관계를 판단하는 과정이 포함됨. 하지만 대소 관계를 판단하는 방법은 요소의 자료형마다 다릅니다.

 

즉, 요소의 자료형은 정수일 수도 있고 문자열이나 구조체일 수도 있다. 그러므로 두 값을 비교하고 난 다음의 어떤 값을 반환하는 비교함수는 사용자가 직접 작성해야한다.

 

1. 첫 번째 인수가 가리키는 값이 더 작으면 음수 반환
2. 첫 번째 인수가 가리키는 값과 두 번째 인수가 가리키는 값이 같으면 0 반환
3. 첫 번째 인수가 가리키는 값이 더 크면 양수 반환 

bseach 함수의 호출

위의 코드에서 int_cmp가 받는 인수의 자료형은 int*이고 bseach 함수가 받는 비교 함수의 인수의 자료형은 void*이다. 두 자료형이 다르므로 bseach 함수의 호출에 맞는 형 변환을 해야 한다.

 

int_cmp 함수의 인자는 int*이므로 bseach 함수 내에서 명시적 형 변환이 이루어지는 것을 볼 수 있다.

 

bseach 함수의 반환 값

bseach 함수의 반환 값은 검색을 통해 찾은 요소의 포인터이다. 따라서 그 요소의 인덱스는 포인터 p에서 포인터 arr를 뺀 값으로 얻을 수 있다. (찾은 요소의 위치 - 배열의 위치 = 인덱스) 검색에 실패한 경우 NULL을 반환한다.

 

bseach 함수

bseach 함수의 이용 예제: 난수 생성의 이용

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

struct system{
    char name[10];
    int age;
    int number;
} person[6];

int int_cmp(struct system *a,struct system *b){
    return strcmp(a->name,b->name);
}

int main() {
    int num=6,cnt = 0;
    srand(time(NULL));
    struct system person[6]={
        {"김영준",0,0},
        {"박현규",0,0},
        {"이수진",0,0},
        {"최윤미",0,0},
        {"함진아",0,0},
        {"홍연의",0,0},
    };

    while(cnt < 6){
        person[cnt].age = rand()%20+10;
        person[cnt].number = rand()%900000+21000000;
        cnt ++;
    }


    puts("이름으로 검색합니다.");
    do{
        struct system tmp;
        printf("이름: ");scanf("%s",tmp.name);
        struct system *rst = bsearch(&tmp,
                        person,
                        num,
                        sizeof(struct system),
                        (int(*)(const void *,const void *))int_cmp
                    );
        if(rst == NULL) puts("검색에 실패하였습니다.");
        else{
            printf("검색 성공!\n");
            for(int i=0;i<10;i++)printf("-"); printf("\n");
            printf("이름: %s\n나이: %d\n번호: %d",rst->name,rst->age,rst->number);
            break;

        }
        // else printf("%d는 x[%d]에 있습니다.\n",key,(int)(rst-arr));
    }while(0);
    

}