[자료구조] : 이진탐색 - bsearch 함수(C)

출처 | DO IT C언어 자료구조 입문편

bsearch 함수란?

• 정렬된 배열에서 검색하는 함수다.

• 검색 대상의 배열은 항상 정렬되어 있어야 한다.

• 검색하는 값과 같은 요소가 여러 개 존재하는 경우 항상 가장 앞쪽에 있는 요소를 찾아 내는 건 아니다.

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

  비교함수를 보고 다음 예시를 보자.

#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;

}
int main()
{
	int i, nx, ky;
	int* x;
	int* p;
	puts("bsearch 함수를 사용하여 검색한다.");
	printf("요소 개수를 입력해라 : ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int));
	printf("오름차순으로 입력하세요 : \n");
	printf("x[0] : ");
	scanf_s("%d", &x[0]);
	for (int i = 0; i < nx; i++)
	{
		do {
			printf("x[%d] : ", i);
			scanf_s("%d", &x[i]);
		
		} while (x[i] < x[i - 1]);

	}
	printf("검색 값 : ");
	scanf_s("%d", &ky);

	p = bsearch(&ky, //검색값에 대한 포인터
		x, // 배열 
		nx, // 요소의 개수 
		sizeof(int), // 요소의 크기
		(int(*)(const void*, const void*)) int_cmp); // 비교함수
	if (p == NULL)
	{
		puts("검색값에 실패했습니다.");
		
	}
	else
	{
		printf("%d는 %[%d]에 있습니다. \n", ky, (int)(p - x));
	}
	free(x);
	return 0;


}

<핵심코드 1>

// 첫 번째 인수 a가 가리키는 객체 -> *a의 값과 b가 가리키는 객체 *b의 값이다.
// 앞의 것이 작으면 -1 , 크면1, 같으면 0를 반환 

int int_cmp(const int* a, const int* b) //정수를 비교하는 함수 (오름차순으로 정렬되어 있다.)
{
	if (*a < *b)
	{
		return -1;
	}
	else if (*a > *b)
		return 1;
	else
		return 0;

}


이 식을 삼항 연산자로 표현허면?
int int_cmp(const int* a, const int* b) //정수를 비교하는 함수 (오름차순으로 정렬되어 있다.)
{
   return *a < *b ? -1 : *a > *b ? 1 : 0;
}

<핵심코드2>

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

1. 첫 번째 인수로 사용하는 매개변수는 키 값이다 &ky값이다. = 검색할 값이 저장된 객체에 대한 포인터다.)

2. 두 번째 매개변수는 배열의 포인터다. 이 프로그램에선 검색 대상인 배열 x의 포인터(x)를 전달한다.

3. 세 번째 인수로 전달하는 매개변수는 배열의 요소 개수 == nx다.

4. 네 번째 인수로 전달하는 매개변수는 배열의 요소 크기 == sizeof(int)

5. 첫 번쨰 인수가 가리키는 값이 더 작으면 음수 값을 반환
   5-1) 첫 번째 인수가 가리키는 값과 두 번째 인수가 가리키는 값이 같으면 0를 반환
   5-2) 첫 번째 인수가 가리키는 값이 더 크면 양수 값을 반환한다.
   5-3) 첫 번째 인수 a가 가리키는 객체 -> a의 값과 b가 가리키는 객체 b

6. int_cmp가 받는 인수의 자료형은 int*다. bsearch함수가 받는 비교 함수의 인수의 자료형은 void *다. 서로 자료형이 다르기 때문에 형변환을 시의적절하게 사용해야된다.

   ※함수를 호출 할 때, 두 함수의 자료형이 다르기 때문에 함수의 호출에 맞게 형 변환을 해야한다. 하지만 이와같이 정의하면 호출할 때 형 변환을 하지 않아도 된다.

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

<결과>

이번엔 오름차순이 아닌 내림차순으로 정렬을 실시하겠다.

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

int int_cmpr(const int* a, const int* b)
{

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

}

int main()
{
	int i, nx, key;
	int* x;
	int* p;
	puts("bsearch 함수를 사용하여 검색해라. : ");
	printf("요소 개수 : ");
	scanf_s("%d", &nx);
	x = calloc(nx, sizeof(int));
	printf("내림차순으로 입력하세요\n");
	printf("x[0] :");
	scanf_s("%d", &x[0]); 
	for (i = 1; i < nx; i++)
	{
		do
		{
			printf("x[%d] : ", i);
			scanf_s("%d", &x[i]);
		} while (x[i] > x[i - 1]); // 바뀐부분

	}
	printf("검색 값 : ");
	scanf_s("%d", &key);
	p = bsearch(&key, x, nx, sizeof(int), (int(*)(const void*, const void*))int_cmpr);
	if (p == NULL)
		puts("검색에 실패했습니다.");
	else
		printf("%d는 x[%d]에 있습니다.\n", key, (int)(p-x));

	free(x);
	return 0;



}

함수 포인터에 대해 알아보자.

double func(int); 
//int를 받아들여 double을 반환하는 함수다.

double (*fp)(int); 
// int를 받아들여 double을 반환하는 함수에 대한 포인터 fp의 선언

double *fn(int); 
// int를 받아들여 double에 대한 포인터를 반환하는 함수 선언 

함수 포인터 예제를 살펴보자.

#include <stdio.h>


int sum(int x1, int x2)
{
	return x1 + x2;

}

int mul(int x1, int x2)
{
	return x1 * x2;

}
void kuku(int(*calc)(int, int))
{
	int i, j;
	for (i = 1; i <= 9; i++)
	{
		for (j = 1; j <= 9; j++)
		{
			printf("%3d", (*calc)(i, j));
		}
		putchar('\n');
	}
}

int main()
{
	puts("덧셈표");
	kuku(sum); // 함수 sum에 대한 포인터를 전달하겠다는 의미.
	puts("곱셈표"); 
	kuku(mul);

	return 0;

}

• 배열 이름 == 배열의 첫 번쨰 요소의 포인터와 같다.
• 함수 이름 == 함수에 대한 포인터와 같다.

핵심 코드 1>

void kuku(int(*calc)(int, int)) // sum함수에 대한 포인터를 매개변수 calc로 받아들인다.

{
	int i, j;
	for (i = 1; i <= 9; i++)
	{
		for (j = 1; j <= 9; j++)
		{
			printf("%3d", (*calc)(i, j)); 
         //받아들인 함수에 대한 포인터를 사용하는 코드가 (*calc)(i,j)다.
         //함수에 대한 포인터에 *를 적용한 코드를 실행하면 포인터가 가리키는 함수가 호출된다.
         // kuku(sum) == kuku(int(*calc)(int, int))
         
		}
		putchar('\n');
	}
}

• main <-> int sum(int x, int y) <-> void kuku(int (*p) ( int ,int))

int sum <=> int (*p) 
1. 우선순위가 높기 때문에 (*p)를 생략하면 안된다.


int x1, int x2 <-> (int, int)

함수에 대한 포인터를 통한 함수의 호출을 알아보면,

(*calc)(i,j)라고 했지만 calc(i,j)라고 해도 된다.

왜냐하면  함수 이름 == 함수에 대한 포인터와 같다.

+ 확장 구조체 배열에서 검색하는 예제를 보자.