[C언어] 이진 탐색 (Binary Search)

데이터 집합이 오름차순 정렬되어 있다는 전제 하에 

1. 탐색 범위를 절반(1/2)씩 줄여나가면서

2. 중앙요소 값을 계속해서 비교.

3. 집합의 크기가 n이라 할 때, 최대 비교 횟수 x = Log2n 

(예 : 1000개의 데이터 집합 내에서 최대 10번의 탐색으로 원하는 대상을 찾을 수 있다)

========================================================

/* DataSet [] : 데이터 집합 정보   Size : 데이터 집합의 크기   Target : 찾고자 하는 탐색 대상 */
ElementType BinarySearch(ElementType DataSet[],int Size,ElementType Target){
    
    int Left,Right,Mid;
    
    Left=0;
    Right=Size-1;
 
    while(Left<=Right){ //중앙요소값만 집요하게 비교한다 
        Mid=(Left+Right)/2;
 
        if(DataSet[Mid]==Target){
            return DataSet[Mid];
        }
        else if(DataSet[Mid]<Target){
            Left=Mid+1;
        }
        else{
            Right=Mid-1;
        }
    }
 
    return NULL;
}