[C++] 이분 탐색(Binary Search)

정의

이분탐색이란 검색 범위를 절반씩 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다

• 검색하는 배열의 데이터가 정렬되어 있어야 한다
• 이분탐색은 범위 설정이 헷갈리고 실수하기 쉽다.
• 시간복잡도는 O(logN)

 

이분탐색 while문 설정

• 이분 탐색에서 분배를 잘못하면 무한 루프에 빠지므로 while 탈출 조건을 고려해야 한다

while문 조건	구간 설정	탈출 직전 값
lo < hi	lo = mid+1 hi = mid	lo = hi-1
lo <= hi	lo = mid+1 hi = mid-1	lo = hi
lo+1 < hi	lo = mid hi = mid	lo = hi-2

※ 특정 조건마다 사용하는 것이 다른 줄 알았는데 취향이라고 한다.

 

이분탐색 lo, hi 범위 설정

이분탐색은 정답 범위를 나타낼 수 있어야 한다. 하지만 lo, hi의 잘못된 범위 설정으로 답을 찾지 못할 수 있다.

정답 범위가 0 ~ n 일 때,

1.  hi의 답이 0이 나올 수 있다면, lo = -1

2.  lo의 답이 n이 나올 수 있다면, hi = n+1

 

예시 코드

위에 3번째 조건을 적용한 예시

int binary_search(int lo, int hi, int target) {
    while(lo+1 < hi) {
        int mid = (lo+hi)/2;  
        
        // if(arr[mid] < target) // hi 반환
        if(arr[mid] <= target) // lo 반환
            lo=mid;
        else
            hi=mid;
    }
    return arr[lo];
}

 

STL을 사용한 예시

#include <algorithm>

vector<int> vec;

binary_search(vec.begin(), vec.end())

 

 

출처 이분 탐색(Binary Search) 헷갈리지 않게 구현하기