2.2 이진 검색 (Binary Search)

이진검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

전제 조건은 이미 정렬이 되어 있다는 것이며, 선형 검색보다 좀 더 빠르게 검색할 수가 있다.

 

5

7

15

28

29

31

39

58

68

70

95

위의 배열에서 원소 39를 찾는 과정을 생각해볼 때, 처음으로 중앙에 위치한 요소인 31 부터 검색을 시작한다.

39는 31보다 큰 값이므로, 31이 위치한 인덱스보다 뒤에 원소가 있다는 것을 알 수가 있다.

 

39

58

68

70

95

그러면 범위는 39의 위치인 a[6] 부터 a[10] 까지로 좁힐 수가 있다.

a[6] 에서 a[10] 의 중간 값인 a[8]의 68을 검색하게 되고 찾고자 하는 값 39는 68보다 작기에, a[6] ~ a[8] 에 위치하는 것을 볼 수가 있다.

 

39

58

68보다 앞의 인덱스에 위치한 두 개의 원소에서 39를 찾으면 검색 성공이다.

 

이제 이것을 코드로 구현해보기 위한 준비를 해보자

배열에서 맨 앞의 인덱스를 Pl, 맨 뒤의 인덱스를 Pr, 중앙 인덱스를 Pc라고 지정을 할 때,

 

pl = 0 , pr = n -1 , pc = (n-1) / 2   

 

a[pc] 와 key를 비교하여 같으면 검색 성공인 방법으로써, 검색에 실패하면 계속해서 범위를 좁혀갈 수가 있다.

 

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

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 = (int *)calloc(nx, sizeof(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); //key값 입력하기, 찾고자하는 값
	idx = bin_search(x, nx, ky);
	if (idx == -1)
	{
		puts("검색 실패");
	}
	else
	{
		printf("%d는 x[%d]에 있습니다.\n", ky, idx);
	}
	free(x);

	return 0;
}

이진 검색의 시간 복잡도는 O(logn) 이다.