C 표준 라이브러리의 bsearch 함수

황준하·2022년 3월 1일

C언어 표준 라이브러리(stdlib)에서 제공하는 bsearch 함수를 살펴보자.

검색 대상 배열은 항상 정렬되어 있어야 함.

검색하는 값과 같은 요소가 여러 개 존재 시, 항상 가장 앞쪽 요소를 찾는 것은 아님.

bsearch 함수의 형식은 아래와 같다. Reference: IBM

#include <stdlib.h>
void *bsearch(const void *key, const void *base,
              size_t num, size_t size,
              int (*compare)(const void *key, const void *element));

const void *key : 검색할 요소 객체에 대한 포인터
const void *base : 검색을 실행할 배열의 포인터
size_t num : 배열의 요소 개수
size_t size : 배열의 요소 크기
int (*compare)(const void *key, const void *element) : 비교 함수 포인터 (아래에서 자세히 설명)
- compare() 함수는 직접 만들어야 함.
compare() 함수는 key 값을 배열 element와 비교한 후 다음 값 중 하나를 리턴해야 함.

return 값 의미
0보다 작음 key가 element보다 작음
0 key가 element와 같음
0보다 큼 key가 element보다 큼

return 값	의미
0보다 작음	key가 element보다 작음
0	key가 element와 같음
0보다 큼	key가 element보다 큼

bsearch를 사용한 코드 예시

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable:4996)

int int_cmp(const int* a, const int* b) {  // 정수를 비교하는 함수 (bsearch에 들어가는 cmp 함수), [오름차순]
	if (*a < *b)
		return -1;
	else if (*a > *b)
		return 1;
	else
		return 0;
}

int main() {
	int i, nx, ky;
	int* x;
	int* p;

	printf("Size: ");
	scanf("%d", &nx);
	x = calloc(nx, sizeof(int));  // [ int(4byte) * 요소의 개수 ] 만큼 메모리 할당
	
	for (int i = 0; i < nx; i++) {  // 오름차순으로 입력 받기
		do {
			scanf("%d", &x[i]);
		} while (x[i] < x[i + 1]);
	}
	printf("Search: ");
	scanf("%d", &ky);  // 검색할 key

	p = bsearch(&ky,  // 검색할 key 객체의 포인터
		x,  // 검색할 배열의 포인터
		nx,  // 배열의 요소 개수
		sizeof(int),  // 배열의 요소 크기(size)
		(int(*)(const void*, const void*)) int_cmp  // 비교 함수, 형변환 해야 한다.
	);

	if (p == NULL)
		printf("Key is not here. \n"); // key가 없다.
	else
		printf("index = %d \n", (int)(p - x));  // p가 가지고 있는 값은 bsearch로 찾은 요소의 포인터 값이다.
												// 따라서, 첫 요소를 가리키는 x로 빼주면 key의 index를 구할 수 있다.
	free(x);

	return 0;
}
>> 입/출력

Size: 8
15 18 18 23 39 57 68 72
Search: 18
index = 1

`int (compare)(const void key, const void *element)` 를 자세히 알아보자.

이 괴기한 형태를 알기 위해서, 함수 포인터에 대해 알아야 한다. ref. 위키백과

함수 포인터: 데이터 값을 가리키는 대신, 함수 포인터는 메모리 내에서 실행 가능한 코드를 가리킨다.
함수 포인터의 자료형은 가리키는 함수에 따라 다르다. 아래의 예시를 보자.
- double func(int); : int를 인자로 받아 double을 반환하는 함수
- double (*fp)(int); : int를 인자로 받아 double을 반환하는 함수에 대한 포인터 fp를 선언
  - 포인터에 대한 선언임
- double *fn(int); : int를 받아들여 double에 대한 포인터를 반환하는 함수 선언
따라서, 위 함수 포인터의 뜻은 void 형 포인터를 인자로 받아 int를 반환하는 함수에 대한 포인터 이다.

그렇다면 void형 포인터는 무엇인가?

void 포인터 : 자료형이 정해지지 않은 포인터

void 포인터는 어떤 것이든 주소를 담을 수 있다.

어떤 변수의 주소 값도 담을 수 있고, 함수의 주소 값도 담을 수 있다.
- void형 포인터는 일단 주소 값에만 의미를 두고 포인터 형은 나중에 결정할 때 유용하게 사용된다.

주의: void 포인터는 자료형이 정해지지 않았으므로 값을 가져오거나 저장할 크기도 정해지지 않았다.

따라서, void 포인터는 역참조 할 수 없다.

int num1 = 10;
char c1 = 'a';
int *numPtr1 = &num1;
char *cPtr1 = &c1;
void *ptr;

ptr = numPtr1;        // void 포인터에 int 포인터 저장, 포인터 자료형이 달라도 컴파일 경고가 발생하지 않음
printf("%d", *ptr);   // void 포인터는 역참조할 수 없음. 컴파일 에러
 
ptr= cPtr1;          // void 포인터에 char 포인터 저장
printf("%c", *ptr);   // void 포인터는 역참조할 수 없음. 컴파일 에러