[C언어] 이분검색 알고리즘

int BinarySearch(int *ar,unsigned num,int key)
{
	unsigned Upper, Lower, Mid;

	Lower = 0;
	Upper = num - 1;
	while(1)
	{
		Mid = (Upper + Lower) / 2;

		if(ar[Mid] == key)	return Mid;
		if(ar[Mid] > key)	Upper = Mid - 1;
		else			Lower = Mid + 1;
		if(Upper <= Lower)	return -1;
	}
}
 
void main()
{
	int ar[] = {2, 6, 13, 19, 21, 21, 23, 29, 35, 48, 62, 89, 90, 95, 99, 102, 109, 208, 629};
	unsigned num;
	int key, idx;

	num = sizeof(ar) / sizeof(ar[0]);
	key = 29;
	idx = BinarySearch(ar, num, key);
	if(idx == -1)
	{
		puts("찾는 값이 없습니다.");
	}
	else
	{
		printf("찾는 값은 %d번째에 있습니다.\n",idx);
	}
}

프로그램 실행화면

이분검색 알고리즘은 순차검색 알고리즘 보다 많이 복잡하다. 우선 배열에 숫자 값들이 오름차순으로 정령되도록 해야한다.

삽입과 삭제를 할 때 이 오름차순이 유지되도록 하는 부분을 추가해 주어야 한다. 제일 작은 수는 lower 제일 큰 수는 upper에 그 인덱스가 저장되도록 하고 mid에 그 중간 인덱스를 집어넣는다.

mid에 저장된 값이 key값 보다 크다면 lower의 값은 mid - 1의 값을 넣어 검색 범위를 반틈으로 줄여버린다.

반대로 mid에 저장된 값이 key값 보다 작다면 upper의 값을 mid + 1로 해주어 또 검색 범위를 반틈으로 줄여버린다.

이 작업을 반복하다보면 mid번지에 저장된 값이 key값과 같아질테고 그 값이 찾고 있던 값이다. 반대로 lower와 upper의 값이 lower > upper가 된다면 찾고자 하는 값은 존재하지 않는 것이다.

순차검색 알고리즘보다 복잡한 만큼 속도는 빠르다.