1. 이진 검색 다루기
- 이진 검색(binary search)
- 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘
ex) 오름차순으로 정렬된 배열 {5,7,15,28,29,31,39,58,68,72,95}에서 39 검색
- 배열의 중앙에 위치한 요소인 a[5](31)부터 검색
- 검색값 39는 중앙 요소 a[5](31)보다 큰값 ( 뒤쪽에 존재)
-> 검색 대상을 뒤쪽에 5개 (a[6]~a[10])로 좁힘
- 검색값 39는 중앙 요소 a[8](68)보다 작은 값 (앞쪽에 존재)
-> 검색 대상을 앞쪽에 2개 (a[6]~a[7])로 좁힘
-> 그 중 앞쪽에 위치한 요소인 a[6](39)을 선택하여 원하는 값인지 확인 -> 검색 성공
- pl : 이진 검색 범위의 맨앞 인덱스 , 0으로 초기화
pr : 이진 검색 범위의 맨 뒤 인덱스, n-1로 초기화
pc: 이진 검색 범위의 중앙 인덱스 , (n-1)/2로 초기화
- 이진 검색을 한 단계씩 진행할 때마다 검색범위가 반으로 좁혀짐
1) a[pc] <key 일떄
- 중앙의 다음 요소를 새로운 pl로 보고 뒤쪽으로 범위를 좁힘
- a[pl]~a[pc]는 key값보다 작은 것이 분명하므로 검색대상에서 제외
- 검색 범위는 a[pc+1]~a[pr]로 좁혀짐
- pl값을 pc+1로 업데이트
2) a[pc] >key 일떄
- 중앙의 이전 요소를 새로운 pr로 보고 앞쪽으로 범위를 좁힘
- a[pc]~a[pr]는 key값보다 큰 것이 분명하므로 검색대상에서 제외
- 검색 범위는 a[pl]~a[pc-1]로 좁혀짐
- pr값을 pc-1로 업데이트
- 이진 검색 알고리즘의 종료 조건 (or)
1) a[pc]와 key가 일치하는 경우 -> 검색 성공
2) 검색 범위가 더 이상 없는 경우 -> 검색 실패
- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 이진 검색
//이진 검색
#include <stdio.h>
#include <stdlib.h>
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;
}
int main()
{
int nx,ky;
puts("이진 검색:");
printf("요소 개수:");
scanf("%d",&nx);
int *x =(int*)calloc(nx,sizeof(int));
printf("오름차순으로 입력하세요.\n");
printf("x[0]:");
scanf("%d",&x[0]);
for(int i=1; i<nx; i++)
{
do{
printf("x[%d]:",i);
scanf("%d",&x[i]);
}while(x[i]<x[i-1]); //바로 앞의 값보다 작으면 다시 입력
}
printf("검색값:");
scanf("%d",&ky);
int idx = bin_search(x,nx,ky); //배열 x에서 값이 ky인 요소를 이진검색
if(idx == -1)
puts("검색에 실패했습니다.");
else
printf("%d는 x[%d]에 있습니다.\n",ky,idx);
free(x); //배열 x를 해제
return 0;
}
2. 복잡도 살펴보기
복잡도(complexity)
- 알고리즘의 성능을 객관적으로 평가하는 기준
시간 복잡도 (time complexity)
- 실행에 필요한 시간을 평가한 것
공간 복잡도 (space complexity)
- 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
2.1 선형 검색의 시간 복잡도
int serach(const int a[], int n, int key)
{
int i=0; //1
while(i<n) { //2
if(a[i] == key) //3
return i; //4
i++; //5
}
return -1 //6
}| 단계 | 실행 횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | n/2 | O(n)` |
| 3 | n/2 | O(n) |
| 4 | 1 | O(1) |
| 5 | n/2 | O(n)` |
| 6 | 1 | O(1) |
O(1) :한번만 실행하는 경우
O(n) : n에 비례하는 횟수만큼 실행하는 경우
-O(f(n))과 O(g(n))의 복잡도 계산
-> max(a,b) = a,b 가운데 큰쪽을 나타내는 함수
O(f(n)) + O(g(n)) = O(max(f(n),g(n)))- 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은쪽의 복잡도를 우선시
- 전체 복잡도는 차원이 가장 높은 복잡도 선택
O(1)+O(n)+O(n)+O(1)+O(n)+O(1) = O(max(1,n,n,1,n,1)) = O(n)
2.2 이진 검색의 시간 복잡도
- 이진 검색법을 이용하면 검색할 요소의 범위를 거의 절반씩 줄일 수 있음
int bin_search(const int a[], int n, int key)
{
int pl =0; //1
int pr= n-1; //2
do {
int pc =(pl+pr)/2; //3
if(a[pc] == key) //4
return pc; //5
else if(a[pc] <key) //6
pl=pc+1; //7
else
pr=pc-1; //8
} while(pl<=pr); //9
return -1; //10
}| 단계 | 실행횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | 1 | O(1) |
| 3 | log n | O(log n) |
| 4 | log n | O(log n) |
| 5 | 1 | O(1) |
| 6 | log n | O(log n) |
| 7 | log n | O(log n) |
| 8 | log n | O(log n) |
| 9 | log n | O(log n) |
| 10 | 1 | O(1) |
O(1)+O(1)+O(log n)+O(log n)+O(1)+O(log n)+...O(1) = O(log n)- 복잡도의 대소관계
1 <log n < n <nlog n < n2 < n3< nk < 2n
3. 정렬된 배열에서 검색하는 bsearch 함수 알아보기
bsearch 함수
- c 언어의 표준 라이브러리가 제공하는 다양한 요소의 자료형을 가진 배열에서도 검색 가능한 함수
- bearch ( 검색값에 대한 포인터, 배열 포인터, 배열 요소 개수, 배열 요소 크기, 비교함수)
- 특징
1) 검색 대상의 배열은 항상 정렬되어 있어야 함
2) 검색하는 값과 같은 요소가 여러 개 존재하는 경우, 항상 가장 앞쪽에 있는 요소를 찾아내는 것은 아님
- bsearch 함수를 사용해 오름차순으로 정렬된 배열을 검색
//besearch 함수를 사용해 오름차순으로 정렬된 배열을 검색
#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 nx,ky;
puts("bsearch 함수를 사용하여 검색");
printf("요소 개수:");
scanf("%d",&nx);
int *x =(int*)calloc(nx,sizeof(int)); //요소의 개수가 nx인 int형 배열 생성
printf("오름차순으로 입력하세요.\n");
printf("x[0]:");
scanf("%d",&x[0]);
for(int i=1; i<nx; i++)
{
do {
printf("x[%d]:",i);
scanf("%d",&x[i]);
}while(x[i]<x[i-1]); //바로 앞의 값보다 작으면 다시 입력
}
printf("검색값:");
scanf("%d",&ky);
int *p = (int*)bsearch(
&ky, //검색값에 대한 포인ㅇ터
x, //배열
nx, //요소의 개수
sizeof(nx), //요소의 크기
(int(*)(const void *, const void *))int_cmp //비교함수
);
if(p == NULL)
puts("검색에 실패했습니다.");
else
printf("%d은 x[%d]에 있습니다.\n",ky,(int)(p-x));
free(x); //배열 x를 해제
return 0;
}
비교 함수
- 이진 검색의 검색 과정에는 검색하는 키값과 배열의 요솟값을 비교하여 대소관계를 판단하는 과정 포함
- But 대소관계를 판단하는 방법은 요소의 자료형마다 다름
-> bsearch 함수는 다섯 번째 매개변수로 비교 함수에 대한 포인터를 전달하는 방식
int int_cmp(const int*a, const int*b)
{
if(*a<*b)
return -1;
else if(*a>*b)
return 1;
else
return 0;
}- 비교 대상
-> 첫 번째 인수 a가 가리키는 객체 *a의 값
-> 두 번째 인수 b가 가리키는 객체 *b의 값
- 앞의 것이 작으면 -1, 크면 1, 같으면 0 반환
bsearch 함수의 호출
- 비교 함수 int_cmp가 받는 인수의 자료형은 const int*
- bsearch 함수가 받는 비교함수 인수 자료형은 const void *
- 두 자료형이 다르므로 bsearch 함수의 호출에 맞도록 형변환
int *p = (int*)bsearch ( &ky,x,nx,sizeof(int),(int(*)(const void *,const void*)) int_cmp);
bsearch 함수의 반환값
- 검색을 통해 찾은 요소의 포인터
- 검색에 실패한 경우 널(NULL)포인터 반환
- 찾아낸 요소의 인덱스는 포인터 p에서 첫번째 요소의 포인터 x를 뺀 식 p-x로 얻을 수 있음
- bsearch 함수를 사용하여 내림차순으로 정렬한 배열에서 검색
//besearch 함수를 사용해 내림차순으로 정렬된 배열을 검색
#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 nx,ky;
puts("bsearch 함수를 사용하여 검색");
printf("요소 개수:");
scanf("%d",&nx);
int *x =(int*)calloc(nx,sizeof(int)); //요소의 개수가 nx인 int형 배열 생성
printf("내림차순으로 입력하세요.\n");
printf("x[0]:");
scanf("%d",&x[0]);
for(int i=1; i<nx; i++)
{
do {
printf("x[%d]:",i);
scanf("%d",&x[i]);
}while(x[i]>x[i-1]); //바로 앞의 값보다 크면 다시 입력
}
printf("검색값:");
scanf("%d",&ky);
int *p = (int*)bsearch(
&ky, //검색값에 대한 포인ㅇ터
x, //배열
nx, //요소의 개수
sizeof(nx), //요소의 크기
(int(*)(const void *, const void *))int_cmpr //비교함수
);
if(p == NULL)
puts("검색에 실패했습니다.");
else
printf("%d은 x[%d]에 있습니다.\n",ky,(int)(p-x));
free(x); //배열 x를 해제
return 0;
}
구조체 배열에서 검색하기
-Person은 {이름, 키, 몸무게}의 멤버로 구성된 구조체
-Person을 자료형으로 하는 배열이 검색 대상인 x임
-배열 x의 요소는 이름을 가리키는 멤버 name을 기준으로 오름차순으로 정렬하면서 초기화
//bserach 함수를 사용한 구조체 배열에서의 검색
#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()
{
Person x[] = { //배열 요소는 이름의 오름차순으로 정렬되어 있어야 함
{"A",179,79},
{"B",172,63},
{"C",176,52},
{"D",165,51},
{"E",181,73},
{"F",172,84}
};
int nx = sizeof(x) /sizeof(x[0]); //배열 x의 요소 개수
int retry;
puts("이름으로 검색합니다.");
do {
Person temp;
printf("이름:");
scanf("%s,temp.name");
Person *p = (Person*)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;
}'C언어 > 자료구조' 카테고리의 다른 글
| 4-1 스택이란? (0) | 2023.07.26 |
|---|---|
| 함수 포인터 (0) | 2023.07.25 |
| 3-2장 선형 검색 (0) | 2023.07.25 |
| 3-1장 검색 알고리즘이란? (0) | 2023.07.25 |
| 2-2 구조체란? (0) | 2023.07.24 |
