1. 선형 검색(linear search), 순차 검색(sequential search)
선형 검색(순차 검색)
: 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검섹
- 선형 검색 종료 조건
- 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우
- 검색할 값과 같은 요소를 발견한 경우
1-1. while문을 사용한 방법
/* 선형 검색 */
#include <stdio.h>
#include <stdlib.h>
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색 ---*/
int search(const int a[], int n, int key)
{
int i = 0;
while (1) {
if (i == n)
return -1; /* 검색 실패 */
if (a[i] == key)
return i; /* 검색 성공 */
i++;
}
}
int main(void)
{
int i, nx, ky, idx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("선형 검색");
printf("요소의 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int)); /* 요소의 개수가 nx인 int형 배열을 생성 */
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색 값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky); /* 배열 x의 값이 ky인 요소를 선형 검색 */
if (idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x); /* 배열을 해제 */
return 0;
}1-2. for문을 사용한 방법
while문보다 짧고 간결함.
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(버전 1 : for문) ---*/
int search(const int a[], int n, int key)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == key)
return i; /* 검색 성공 */
return -1; /* 검색 실패 */
}보초법
선형 검색은 반복할 때마다 종료조건 1, 2를 모두 체크함. -> 많은 비용 발생
검색하고자 하는 키 값을 맨 끝 요소에 저장. 저장하는 값을 보초(sentinel)라고 함.
원하는 값이 데이터에 존재하지 않아도 보초까지 검색하면 종료조건 2가 성립함.
따라서 종료조건 1이 없어도 된다.
종료 판단 조건을 2회 -> 1회로 줄이는 역할을 함.
/* 선형 검색(보초법) */
#include <stdio.h>
#include <stdlib.h>
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 선형 검색(보초법) ---*/
int search(int a[], int n, int key)
{
int i = 0;
a[n] = key; /* 보초를 추가 */
while (1) {
if (a[i] == key)
break; /* 원하는 키 값을 찾은 경우 */
i++;
}
return i == n ? -1 : i;
}
int main(void)
{
int i, nx, ky, idx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("선형 검색(보초법)");
printf("요소의 개수 : ");
scanf("%d", &nx);
x = calloc(nx + 1, sizeof(int)); /* 요소의 개수(nx + 1)인 int형 배열을 생성 */
for (i = 0; i < nx; i++) { /* 주의 : 값을 읽어 들인 것 nx 개 */
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
printf("검색 값 : ");
scanf("%d", &ky);
idx = search(x, nx, ky); /* 배열 x에서 값이 ky인 요소를 선형 검색 */
if (idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d(은)는 x[%d]에 있습니다.\n", ky, idx);
free(x); /* 배열을 해제 */
return 0;
}2. 이진 검색
-
조건
데이터의 키 값이 이미 오름차순 또는 내림차순으로 정렬됨
-
이진 탐색의 시간 복잡도
참고) https://jwoop.tistory.com/9
/* 이진 검색 */
#include <stdio.h>
#include <stdlib.h>
/*--- 요소의 개수 n인 배열 a에서 key와 일치하는 요소를 이진 검색 ---*/
int bin_search(const int a[], int n, int key)
{
int pl = 0; /* 검색 범위 맨 앞의 인덱스 */
int pr = n - 1; /* 검색 범위 맨 끝의 인덱스 */
int pc; /* 검색 범위 한가운데의 인덱스 */
do {
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; /* 검색 실패 */
}
int main(void)
{
int i, nx, ky, idx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("이진 검색");
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", &ky);
idx = bin_search(x, nx, ky); /* 배열 x에서 값이 ky인 요소를 이진 검색 */
if (idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d는(은) x[%d]에 있습니다.\n", ky, idx);
free(x); /* 배열 해제 */
return 0;
}복잡도(Complexity)
- 시간 복잡도 : 실행에 필요한 시간을 평가
- 공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
복잡도와 증가율
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*));
bsearch(키 값, 배열의 포인터, 배열의 요소 개수, 배열의 요소 크기, 두 요소를 비교하기 위한 함수 포인터)
const void *key: 찾으려는 자료의 포인터 주소const void *base: 찾는 대상이 되는 테이블 포인터 주소- 두 요소를 비교하기 위한 함수 포인터
(리턴값이 양수이면 오른쪽, 음수이면 왼쪽)
- 반환 : 일치하는 요소에 대한 포인터를 반환, 일치하는 요소가 없다면 NULL 포인터를 반환
- 조건 : 검색 대상의 배열은 항상 정렬되어 있어야 한다.
/* 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 int_cmp(const int *a, const int *b)
// {
// return *a<*b ? -1: *a>*b ? 1 : 0;
// }
/*--- 캐스팅(casting)없이 사용할 수 있는 비교함수 ---*/
// 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;
// }
int main(void)
{
int i, nx, ky;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
int *p; /* 검색한 요소에 대한 포인터 */
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", &ky);
p = bsearch(&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 int_cmp(const int *a, const int *b)
{
if (*a < *b)
return -1;
else if (*a > *b)
return 1;
else
return 0;
}/*--- 정수를 비교하는 함수(내림차순) ---*/
int int_cmpr(const int *a, const int *b)
{
if (*a < *b)
return 1;
else if (*a > *b)
return -1;
else
return 0;
}구조체 배열에서 검색하기
/*--- Person형의 비교 함수(오름차순으로 이름 정렬) ---*/
int npcmp(const Person *x, const Person *y)
{
return strcmp(x->name, y->name);
}strcmp()
str1 < str2 : 음수반환
str1 > str2 : 양수반환
str1 == str2 : 0반환
/* 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;
}
일단 할 수 있는걸 하자.