Page 116 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

bsearch 함수(정렬된 배열에서 검색하는 함수)

C 언어의 표준 라이브러리는 다양한 요소의 자료형을 가진 배열에서도 검색 가능한 bsearch
함수를 제공합니다. 이 함수를 일반 유틸리티(utility) 함수라고 부릅니다. 다음에 bsearch 함
수의 특징과 요소를 표로 정리했습니다.

06장에서 살펴볼 정렬을 수행하는 qsort 함수도 유틸리티 함수입니다.

특징 1. 검색 대상의 배열은 항상 정렬되어 있어야 합니다.
특징 2. 검색하는 값과 같은 요소가 여러 개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내는 건 아닙니다.

bsearch 함수
헤더 #include <stdlib.h>
void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
형식
int(*compar)(const void *, const void *));
맨 처음 요소를 base가 가리키는 요소의 개수가 nmemb개이고 요소 크기가 size인 객체의 배열에서 key
가 가리키는 객체와 일치하는 요소를 검색합니다.
compar가 가리키는 비교 함수는 key 객체에 대한 포인터를 첫 번째 인수로, 배열 요소에 대한 포인터
해설 를 두 번째 인수로 하여 호출합니다. compar가 가리키는 비교 함수는 key 객체가 배열 요소보다 작으면
작은 값을, 일치하면 0을, 크면 큰 값을 반환하도록 작성해야 합니다. compar가 가리키는 배열은 key
객체와 비교가 가능한 작은 요소, 같은 요소, 큰 요소의 세 부분으로 구성되어 있습니다. 이 세 부분이
소개한 순서로 존재해야 합니다.
검사하는 대상(배열) 중에 일치하는 요소에 대한 포인터를 반환합니다. 일치하는 요소가 없다면 NULL
반환값
포인터를 반환합니다. 두 요소의 값이 같을 때 어느 요소와 일치하는지는 규정되어 있지 않습니다.

실습 3-5는 bsearch 함수를 사용해 작성한 프로그램입니다. 오름차순으로 정렬된 배열 x의

요소에서 입력한 값 ky와 같은 요소를 찾습니다. 이때 bsearch 함수를 호출하는 곳이 실습 코
드의 초록색으로 표시한 부분입니다. 강력한 기능의 함수인 만큼 사용 방법도 어렵고 인수도
5개나 필요합니다.

1. 첫 번째 인수로 전달하는 매개변수는 키 값입니다(검색할 값이 저장된 객체에 대한 포인터). 이 프로그램에
서는 키 값이 변수 ky에 저장되어 있으므로 &ky를 전달합니다.
2. 두 번째 인수로 전달하는 매개변수는 배열의 포인터입니다. 이 프로그램에서는 검색 대상인 배열 x의 포인
터(x)를 전달합니다.
3. 세 번째 인수로 전달하는 매개변수는 배열의 요소 개수입니다. 이 프로그램에서는 nx입니다.
4. 네 번째 인수로 전달하는 매개변수는 배열의 요소 크기입니다. 이 프로그램에서는 검색 대상인 배열 x의 요
소의 자료형이 int형이므로 sizeof(int)를 전달합니다.
5. 가장 복잡한 것이 다섯 번째 인수입니다. 이 내용에 대해서는 바로 다음에 설명하겠습니다.

116 C 알고리즘