[C-알고리즘] 이분검색

 

순차검색은 처음부터 맨 끝까지 차례대로 검색하는 반면

이분검색은 자료의 범위를 반씩 줄여가면서 검색한다. 

( 단 이분검색은 데이터가 정렬되어 있어야 가능하다 )

 

최대 검색 횟수는 log(2)N로 매우 빠른속도로 자료를 찾는다.

 

 

- 로그 공식 - 

만약 자료가 100개인 어떤 데이터를 찾는다고 하면 log(2)100  =>

= 6

최소 6번의 비교를 통해 찾아낸다. 

 

 

 

#include <stdio.h>
 
#define FIND 62
 
int main()
{
    int data[10] = { 6,13,21,30,40,51,62,79,87,100 };
    
    int L = 0 , R = 9;  
  int M , search = 0 , count = 0;
        
    do {
        
        count++; // 검색 횟수  
        
        M = (L + R) / 2; 
        
        if ( data[M] == FIND )
        { search = 1; break; }
        else if ( FIND > data[M] ) L = M+1;
        else R = M-1;                
        
    } while( L <= R );
 
    
    printf("찾으려고 하는 값이 존재%s\n검색 횟수 %d\n",
    (char *[]){"하지 않습니다.","합니다."}[search] , count );
        
}

 

---

L(시작위치)과 R(끝위치)을 더하여 M(중간위치)을 계산한 후 

 

찾으려고 하는 값이 자료값보다 크면 L을 (M+1) 오른쪽으로 이동시키고 ,  

작으면 R을 (M-1) 왼쪽으로 이동시킨다.

 

검색이 끝나는 조건은 시작위치가 끝위치보다 커질 때다.

---

 

 

 

찾으려고 하는 값이 62일 때 L , R , M의 변화

---

 

[1]     L : 0   R : 9   M : 4
[2]     L : 5   R : 9   M : 7
[3]     L : 5   R : 6   M : 5
[4]     L : 6   R : 6   M : 6
 
찾으려고 하는 값이 존재합니다.
검색 횟수 4