이진 탐색 (Binary Search)

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

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;

}

댓글