[Algorithm] 이진 탐색 (Binary Search)

I. 이진 탐색 (Binary Search)의 개요

가. 이진 탐색의 정의

정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식

 

나. 이진 탐색의 특징

• 분할과 정복 기반
• 정렬된 데이터 집합에서 사용
• 고속 탐색

 

Ⅱ. 이진 탐색 단계 및 사례

가. 이진 탐색 단계 및 사례

- 데이터 집합의 가운데 있는 기준값과 찾는 키 값 비교 (1) 찾는 키 값 > 기준 값 : 오른쪽 부분 검색 (2) 찾는 키 값 < 기준 값 : 왼쪽 부분 검색 - 키 값을 찾을 때까지 이진 검색을 순환적으로 반복

/*searchnum 에 대해 list [0]<=list[1]<= …<=list[n-1]을 탐색 찾으면 그 위치를 반환하고 못 찾으면 –1을 반환한다.*/ int binsearch(int list[],int searchnum, int left,int right) { int middle; while(left <= right) { middle = (left + right) / 2; /* middle 값 계산 */ switch(COMPARE(list[middle],searchnum)) { case -1: left = middle + 1; break; case 0: return middle; case 1: right = middle - 1; break; }} return -1; }