OBG WiKi

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

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

===== 예제 =====
<file cpp 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);
	}
}
</file>

===== 참고 =====
  * [[http://en.wikipedia.org/wiki/Binary_search_algorithm|위키피디아]] \\
  * [[http://soen.kr/lecture/ccpp/cpp2/20-1-2.htm|김상형 씨 홈페이지]] \\

사용자 도구

문서 도구

OBG WiKi

사이트 도구