[알고리즘] 이진 검색

이진 검색

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.

이진 검색 알고리즘의 적용 전제조건은 '데이터가 키 값으로 이미 정렬된 상태' 이다.

선형 검색보다는 조금 더 빠르다.

'범위 중앙 찍고 비교하고, 검색범위 좁히고 범위 중앙 찍고 비교하고....' 방식

 

//요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 이진 검색
int bin_search(const int a[], int n, int key) {
    
    int pl = 0; // 검색 범위 맨 앞의 인덱스
    int pr = n - 1; // 검색 범위 맨 끝의 인덱스
    int pc; // 검색 범위 가운데의 인덱스
    
    do {
        pc = (pl + pr) / 2;
        if(a[pc] == key) // 검색 성공
            return pc;
        else if(a[pc] < key)
            pl = pc + 1;
        else
            pr = pc - 1;
    } while(pl <= pr);
    
    return -1; // 검색 실패
}

 

 

분석

이진 검색의 평균 횟수 : log n

시간복잡도 : O(log n)