이진 검색(Binary Search)

1. 개념

이미 정렬된 자료에 대한 검색 알고리즘. 파일을 이분화하면서 검색 대상이 되는 키 값과 중간 위치의 값을 비교하면서 검색하는 방법.

앞에서부터 하나하나 검색하는 순차 검색보다 보다 효율성이 높다.

한번 비교할때마다 검색의 범위가 반으로 줄어드므로 수행 복잡도는 최소 O(log^n)

2. 과정

① 정렬된 데이터에서 첫 번재 위치를 left, 마지막 위치를 right로 설정

② middle 값을 구한다. (middle = (left + right) / 2)

③ middle 값이 찾고자 하는 데이터이면 검색을 종료.

   찾고자 하는 데이터가 아닐떄,

   1) 찾고자 하는 값 > middle 값일때

   left = middle+1로 재설정 후 2~3번의 과정 반복

   2) 찾고자 하는 값 < middle 값일때

   right = middle-1로 재설정 후 2~3번의 과정 반복

④ left>right이 되면 검색 종료(찾고자 하는 데이터 값이 없음)

3. Code

#include <stdio.h>

int binary_search(int a[], int n, int key) {
	int left, right, middle;
	left = 0;
	right = n-1;
	
	while(!(left>right)) {
		middle = (left+right)/2;
		if(key>a[middle])
			left = middle+1;
		else if(key<a[middle])
			right = middle-1;
		else
			return middle;
	}
	
	return -1;
}

int main() {
	int i, key, find, count;
	int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
	
	count = sizeof(array)/sizeof(int);
	printf("array[] 데이터 : ");
	for(i=0;i<count;i++) {
		printf("%d\t", array[i]);
	}
	printf("\n");
	
	printf("찾고자 하는 데이터를 입력해주세요 : ");
	scanf("%d", &key);
	
	find = binary_search(array, count, key);
	if(find > -1)
		printf("array[%d] = %d", find, array[find]);
	else
		printf("값이 존재하지 않습니다.\n");
}