[C언어] 이분검색 예제 소스

이분검색(binary search)는 데이터가 정렬되어 있다는 가정하에 실행합니다.

O(n) = log2N으로 데이터의 양이 많더라도 그 크기에 큰 영향을 받지 않아 매우 좋은 것으로 알려져 있습니다.

[C언어] 이분검색 예제 소스

#include <stdio.h>

int binarysearch(int data[], int n, int find_key);
void printarray(int data[], int n);

int main()
{
	int narray[10]={1,2,3,4,5,6,7,8,9,10};
	int a;
	int nindex;

	printarray(narray,10);

	// 찾을 값을 입력 받음
	printf("찾는 값은?\n");
	scanf("%d",&a);

	// 이분검색
	nindex = binarysearch(narray,10,a);

	// 결과값 출력
	if (nindex >= 0)
		printf("found %d at %d\n",a, nindex);
	else
		printf("not found.\n");
	return 0;
}

// 이분검색 함수
int binarysearch(int data[], int n, int find_key)
{
	int mid = 0;
	int left = 0;
	int right = n-1;

	while (left >= right)
	{
		mid = (left + right ) / 2 ;

		if(find_key == data[mid])
			return mid;
		else if(find_key < data[mid])
			right = mid -1;
		else if(find_key > data[mid])
			left = mid +1;
	}

	return -1;
}

// 배열안에 있는 값을 출력하는 함수
void printarray(int data[], int n)
{
	int i;
	for ( i=0; i<n; i++)
		printf("%d ",data[i]);
	printf("\n");

}