이진 검색의 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(Sort)되어 있다는 것입니다.
아래의 이진 검색 알고리즘은 아래와 오름차순으로 정렬이 되어있단 가정하에 key값을 찾습니다.
int bin_search(const int a[], int n, int key) {
int pl = 0; // 검색 범위 맨앞 인덱스
int pr = n - 1; // 검색 범위 맨뒤 인덱스
do {
int pc = (pl + pr) / 2; // 중앙 요소 인덱스
if (a[pc] == key)
return pc; // 검색 성공
else if (a[pc] < key) // 검색 범위를 뒤쪽 반으로 줄임
pl = pc + 1;
else // 검색 범위를 앞쪽 반으로 줄임
pr = pc - 1;
} while (pl <= pr); // 검색 범위의 맨앞 인덱스가 맨뒤 인덱스를 넘지 않을때 반복
return -1; // 검색 실패
}알고리즘 종료 조건에는 다음과 같은 경우가 있습니다.
1. a[pc]와 key가 일치하는 경우
2. 검색 범위가 더이상 없는 경우
아래의 그림으로 key 값을 찾는 과정을 봅시다. 배열에서 7을 검색하는 과정입니다.
- a[pc]와 key가 일치하는 경우
a[pc]의 값이 7과 일치하면 7이 들어있는 배열의 인덱스(pc)를 반환합니다.
- 검색 범위가 더이상 없는 경우
검색 범위가 없을 경우, 즉, pl > pr을 만족 할경우 -1를 반환합니다.
- 알고리즘의 조건식을 살펴봅시다.
a[pc] < key, a[pc] > key, a[pc] == key 가 있습니다.
key 값을 기준으로 중앙값을 비교하여 검색 범위를 매번 반으로 줄이며, 읽지 않아도 되는 값들을 버리는 것입니다. 따라서 이진 검색 알고리즘의 복잡도는 밑이 2인 O(logn)입니다.
bsearch 함수
C 언어의 표준 라이브러리는 다양한 요소의 자료형을 가진 배열에서도 검색 가능한 bsearch 함수를 제공합니다. 이 함수를 일반 유틸리티(utility) 함수라고 부릅니다.
특징 1. 검색 대상의 배열은 항상 정렬되어 있어야함
특징 2. 검색하는 값과 같은 요소가 여러개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내는 건 아님
- 헤더 : #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, 요소의 크기가 size인 객체의 배열에서 key가 가르키는 객체와 일치하는 요소를 검색
- 반환값 : 검사하는 대상(배열) 중에 일치하는 요소에 대한 포인터(주소) 반환
- 주의사항 : 두 요소의 값이 같을 때 어느 요소와 일치하는지 규정 되어있지 않음
besearch 함수를 사용해서 실습을 해보겠습니다.
/* bsearch 함수를 사용하여 오름차순으로 정렬된 배열을 검색 */
#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, key;
int* x = NULL; /* 배열의 첫 번째 요소에 대한 포인터 */
int* p = NULL; /* 검색한 요소에 대한 포인터 */
puts("bsearch 함수를 사용하여 검색");
printf("요소의 개수 : ");
scanf("%d", &nx);
x = 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", &key);
p = bsearch(&key, /* 검색 값에 대한 포인터 */
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;
}- 첫 번째 인수로 전달하는 매개변수는 키 값입니다(검색할 값이 저장된 객체에 대한 포인터), 키 값이 변수 key에 저장되어 있으므로 &key를 전달합니다.
- 두 번째 인수로 전달하는 매개변수는 배열의 포인터입니다. 검색 대상인 배열 x의 포인터를 전달합니다.
- 세 번째 인수로 전달하는 매개변수는 배열의 요소 개수입니다. 검색 대상인 x배열의 요소의 개수인 nx 매개변수를 전달합니다.
- 네 번째 인수로 전달하는 매개변수는 배열의 요속 크기 입니다. 검색 대상인 x배열의 요소의 자료형이 int형이므로 sizeof(int)를 잔달합니다.
- 다섯 번째 인수가 가장 복잡합니다. (int(*)(const void *, const void *)) 부분은 생략이 가능하며, int_cmp 함수의 이름 자체가 포인터 처럼 쓰여 이름을 전달합니다. 따라서 함수 안의 매개변수는 기재할 필요가 없습니다. 이 내용은 뒤에서 자세한 설명을 드리겠습니다.
맨 위 그림과 같이 예제를 입력하면 잘 실행되는 것을 볼 수 있습니다.
bsearch 다섯번째 인수인 바교함수
int int_cmp(const int* a, const int* b)
{
if (*a < *b)
return -1;
else if (*a > * b)
return 1;
else
return 0;
}이진 검색의 검색 과정에는 검색하는 값과 배열의 요소값을 비교하여 대소 관계를 판단하는 과정이 포합됩니다. 대소를 판단하는 방법은 요소의 자료형마다 다릅니다. 자료형은 정수, 문자열 혹은 구조체일 수도 있습니다. 그러므로 두값을 비교하고 난 다음의 어떤 값을 반환하는 비교 함수는 사용자가 직접 작성해야 합니다. 따라서 bsearch 함수는 다섯번째 매개변수로 이 비교 함수에 대한 포인터를 전달하는 방식입니다.
bsearch 함수의 반환값
p = bsearch(&key, /* 검색 값에 대한 포인터 */
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));bsearch 함수의 반환값은 검색을 통해 찾은 요소의 포인터입니다.
p는 bsearch 함수의 반환값을 대입한 p는 찾은 요소를 가리킵니다. 따라서 그 요소의 인덱스는 포인터 p에서 첫 번째 요소의 포인터 x를 뺀 식 p-x로 얻을 수 있습니다. 예를 들어, x의 값이 0x62FE40이고 p의 값이 0x62FE48이면 p-x는 8byte 이고 int형은 요소당 4byte이므로 인덱스는 2입니다. 또한 bsearch 함수는 검색에 실패한 경우 NULL 포인터를 반환합니다.
bsearch 함수의 호출
비교함수 int_cmp가 받는 인수의 자료형은 int *이고 bsearch 함수가 받는 비교 함수의 인수의 자료형은 void *입니다. 두 자료형이 다르므로 bsearch 함수의 호출에 맞도록 형 변환을 해야합니다.
p = bsearch(&key, /* 검색 값에 대한 포인터 */
x, /* 배열 */
nx, /* 요소의 개수 */
sizeof(int), /* 요소의 크기 */
(int(*)(const void*, const void*)) int_cmp /* 비교 함수 */
);int_cmp를 아래와 같이 정의하면 호출할 때 현 변환을 하지 않아도 됩니다. 대신 비교 함수 안에서 형 변환을 많이 할 수도 있으므로 필요에 따라 함수를 구현하여 형 변환하면 됩니다.
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;
}void *형의 포인터 a를 int *형으로 형 변환한 포인터를 간접 연산자 *를 적용하여 *(int *)a는 int형 포인터 a가 가리키는 객체의 *a값을 나타냅니다.
위의 함수 정의는 캐스팅 없이 사용하 수 있는 비교 함수를 구현하였습니다.
Cast는 형 변환이라고 하며 특정한 형으로 자료형을 변환하는 연산자입니다. 예를 들어, int형 변수를 나눗셈할 때 소수점 아래에 자리가 생기는 경우가 있는데, 이때 캐스팅을 하지 않으면 소수점 아래의 값이 사라집니다. 이를 해결하려면 int형 변수를 나눗셈할 떄 double형으로 변환하고 그 결과를 double형 변수에 저장하여야 소수점 아래의 값을 얻을 수 있습니다.
함수 포인터
bsearch 함수의 호출의 다섯번째 인수를 보면 특이한 점을 볼 수 있습니다.
여기서 짚고 넘어가야할 개념인 함수 포인터를 알아보겠습니다.
함수 포인터는 이름 그대로 함수를 가리키는 포인터입니다. 함수 포인터의 자료형은 가리키는 함수에 따라 다릅니다.
아래처러 선언한 함수를 살펴보겠습니다.
double func(int); // int를 받아들여 double을 반환하는 함수
double(*fp)(int); // int를 받아들여 double을 반환하는 함수에 대한 포인터 fp의 선언
double *fn(int); // int를 받아들여 double에 대한 포인터를 반환하는 함수 선언double *fn(int) 처럼 변수 이름 앞에 *를 붙이는 것은 객체에 대한 포인터의 선언과 같습니다. 다만 변수 이름을 ()로 감싸야합니다. ()를 생략하여 double 형에 대한 포인터를 반환하는 함수의 선언이 됩니다.
아래의 실습예제를 보면 잘 이해가 됩니다. 함수에 대한 포인터를 사용하여 '덧셈표'와 '곰셈표'를 출력하는 프로그램입니다. kuku 함수에서 실인수로 주어진 sum과 mul은 모두 함수 이름입니다.** 배열 이름이 배열의 첫 번째 요소의 포인터와 같다고 이해하였듯이 함수 이름은 그 함수에 대한 포인터와 같다고 생각하면 됩니다.**
- kuku(sum)
- 함수 sum에 대한 포인터를 전달
- 포인터가 가리키는 함수의 실행으로 얻은 계산 결과 출력
- void kuku(int(*calc)(int, int))
- 호출된 kuku 함수는 sum 함수에 대한 포인터를 매개변수 calc로 받아들임
- int sum(int x1, int x2) 처럼 sum() 안에 매개변수의 자료형을 넣어 주듯이 kuku() 안에 함수 포인터에 대한 자료형을 넣어준다.
- (*calc)(i, j)
- 받아들인 함수에 대한 포인터를 사용하는 코드
- 포인터 calc가 가리키는 함수를 호출하는 코드는 프로그램을 컴파일할 때가 아니라 실행할 때 실제로 어떤 함수를 호출할지 결정함
- 간접 연산자 *를 적용한 코드를 실행하면 그 포인터가 가리키는 함수가(sum, mul) 호출됨 : 마치 객체를 가리키는 포인터에 간접 연산자를 적용하면 그 객체의 실제 자료에 접근할 수 있는 것과 같음
- 주의사항 : *calc를 둘러싸는 ()를 생략할 수 없다. 간접 연산자 *보다 함수를 호출하는 연산자()가 우선 순위가 높다.
/* 덧셈표와 곱셈표 */
#include <stdio.h>
/*--- x1과 x2의 합을 구합니다. ---*/
int sum(int x1, int x2)
{
return x1 + x2;
}
/*--- 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(void)
{
puts("덧셈표");
kuku(sum);
puts("\n 곱셈표");
kuku(mul);
return 0;
}위와 같이 함수에 대한 포인터를 사용하면 호출하는 함수를 실행하여 결정하는 동적 함수 호출을 구현할 수 있습니다. 동적 함수 호출을 사용하면 사용자가 원하는 경우에 sum 함수와 mul 함수를 직접 작성하여 호출하지 않아도 실행할 수 있습니다.
함수에 대한 포인터 표현
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 *p를 int p[]로 선언하는 경우와 비슷합니다.
함수에 대한 포인터를 통한 함수의 호출
일반적으로 함수 호출식의 왼쪽 피연산자는 함수 포인터가 안닌 함수 이름을 사용해도 됩니다. 간단히 (*calc)(i, j)를 calc(i, j)라고 해도 됩니다.
구조체 배열에서 검색하기
자료형이 구조체인 배열에서의 검색을 bsearch 함수로 구현해보겠습니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char name[10]; /* 이름 */
int height; /* 키 */
int weight; /* 몸무게 */
} Person;
/*--- Person형의 비교 함수(오름차순으로 이름 정렬) ---*/
int npcmp(const Person* x, const Person* y)
{
return strcmp(x->name, y->name);
}
int main(void)
{
Person x[] = { /* 배열 요소는 이름의 오름차순으로 */
{ "김영준", 179, 79 }, /* 정렬되어 있지 않으면 안 됩니다. */
{ "박현규", 172, 63 },
{ "이수진", 176, 52 },
{ "최윤미", 165, 51 },
{ "함진아", 181, 73 },
{ "홍연의", 172, 84 },
};
int nx = sizeof(x) / sizeof(x[0]); /* 배열 x의 요소의 개수 */
int retry;
puts("이름으로 검색합니다.");
do {
Person temp, * p;
printf("이름 : ");
scanf("%s", temp.name);
p = bsearch(&temp, x, nx, sizeof(Person),
(int(*)(const void*, const void*)) npcmp);
if (p == NULL)
puts("검색에 실패했습니다.");
else {
puts("검색 성공 !! 아래 요소를 찾았습니다.");
printf("x[%d] : %s %dcm %dkg\n",
(int)(p - x), p->name, p->height, p->weight);
}
printf("다시 검색할까요? (1) 예 / (0) 아니오 : ");
scanf("%d", &retry);
} while (retry == 1);
return 0;
}실행결과
구조체 Person은 {이름, 키, 몸무게의 멤버}로 구성되어 있습니다.
Person을 자료형으로 하는 배열이 검색 대상인 x입니다. 배열 x의 요소는 이름인 멤버 name을 기준으로 오름차순으로 정렬하면서 초기화합니다.
비교함수 npcmp는 두 문자열 x->name과 y->name의 대소 관계를 strcmp 함수를 호출하여 비교합니다. strcmp 함수의 반환값은 다음과 같습니다.
- x->name이 y-<name 보다 작으면 음수
- x->name이 y-<name 보다 크면 양수
- x->name이 y-<name이 같으면 0
