테이블의 중간값과 비교하고 테이블을 절반으로 나누어, 키값과의 대소에 따라 검색할 테이블을 다시 선택하는 방식. 단, 이진 검색을 하려면 테이블의 자료들이 정렬되어 있어야 한다. 비교할 데이터가 절반씩 줄어들기 때문에 데이터가 1천개일 때 최대 10번, 1백만개일 때 최대 20번만 비교하면 원하는 데이터를 찾을 수 있다.

binary_search.cpp

#include <stdio.h>
#include <stdlib.h>
 
int BinarySearch(int *ar,unsigned num,int key)
{
	unsigned Upper,Lower,Mid;
 
	Lower=0;
	Upper=num-1;
	for (;;) {
		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);
	}
}

• 위키피디아
  
• 김상형 씨 홈페이지