bsearch 함수 구현

링크텍스트 이 링크는 이진검색의 자세한 검색과정이 있습니다. 검색과정을 이해하고 이 글을 봐주셔야 이해가 수월합니다.

bsearch 함수와 같은 형식으로 호출할 수 있는 함수를 구현해봅시다.
아래의 binsearch 함수는 bsearch와 동일한 함수입니다.

• 자료형은 정수, 문자, 문자열, 구조체등 모두 사용할 수 있습니다. 그치만 대소 관계를 판단하는 방법은 요소의 자료형마다 다릅니다. 그러므로 두 값을 비교하고 난 다음의 어떤 값을 반환하는 비교 함수는 사용자가 직접 작성해야 합니다.

아래는 오름차순으로 정렬된 배열을 이진검색을 통해 키값을 찾아내는 알고리즘입니다. 전체적으로 코드를 살펴본 후 bsearch(binsearch) 함수를 자세히 알아봅시다.

/* bsearch 함수를 사용하여 오름차순으로 정렬된 배열을 검색 */
#pragma warning (disable:4996)
#include <stdio.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;
}
void* binsearch(const void* key, const void* base, size_t nmemb, size_t size, int(*compar)(const void*, const void*))
{
	size_t pl = 0;			// 검색 범위 맨앞 인덱스
	size_t pr = nmemb;		// 검색 범위 맨뒤 인덱스
	size_t pc;			// 중앙 요소 인덱스
	char* x = (char*)base;
	if(nmemb > 0) {
		while (1) {
			int comp = compar(&x[(pc = (pl + pr) / 2) * size], key);
			if (comp == 0)		// 검색 성공
				return &x[pc * size];
			else if (pl == pr)	// 검색 범위의 맨앞 인덱스가 맨뒤 인덱스를 넘지 않을때 반복 
				break;
			else if (comp < 0)  	// 검색 범위를 뒤쪽 반으로 줄임
				pl = pc + 1; 
			else
				pr = pc - 1;	// 검색 범위를 앞쪽 반으로 줄임
		}
	}
	return NULL; // 검색 실패
}
int main(void)
{
	int i, nx, ky;
	int* x = NULL;		 /* 배열의 첫 번째 요소에 대한 포인터 */
	int* p = NULL; 	        /* 검색한 요소에 대한 포인터 */

	puts("bsearch 함수를 사용하여 검색");
	printf("요소의 개수 : ");
	scanf("%d", &nx);
	x = (int*)calloc(nx, sizeof(int)); 	/* 요소의 개수 nx인 int형 배열을 생성 */

	printf("오름차순으로 입력하세요.\n");
	printf("x[0] : ");
	scanf("%d", &x[0]);
	for (i = 1; i < nx; i++) {
		do {
			printf("x[%d] : ", i);
			scanf("%d", &x[i]);
		} while (x[i] < x[i - 1]); 	/* 바로 앞의 값보다 작으면 다시 입력 */
	}

	printf("검색 값 : ");
	scanf("%d", &ky);
	p = (int*)binsearch(&ky, 		/* 검색 값에 대한 포인터 */
		x,	 			/* 배열 */
		nx,			        /* 요소의 개수 */
		sizeof(int),									/* 요소의 크기 */
		(int(*)(const void*, const void*)) int_cmp 	/* 비교 함수 */
	);

	if (p == NULL)
		puts("검색에 실패했습니다.");
	else
		printf("%d는 x[%d]에 있습니다.\n", ky, (int)(p - x));

	free(x); 		/* 배열을 해제 */

	return 0;
}

메인함수 int *x

• int형은 4byte씩 메모리가 할당되며 위와 같이 주소를 보면 알수 있습니다.
  
  
  

binsearch함수 char *x

char *x = (char*)base;
void 포인터형으로 받은 매개변수 base를 char 포인터로 자료형 변환

int comp = compar(&x[(pc = (pl + pr) / 2) * size], key);

• char형은 1byte, int형은 4byte입니다. 따라서 배열의 요소는 4배 차이가 나므로 int형으로 변환해줄 경우 메모리 공간이 3byte만큼 더 필요합니다. size로 받은 매개변수(요소의 크기)는 int형이므로 4입니다. x배열 인덱스에 size를 곱하여 여유공간을 만듭니다. 즉, 반환해줄 요소의 크기만큼 메모리 공간을 알맞게 할당하는 \것입니다.
• binsearch 함수 내의 검색할 배열을 char *로 구현하면 문자, 문자열, 정수모두 변환이 유용합니다.