[C++] 이분 탐색으로 lower_bound, upper_bound 구현하기

이분 탐색으로 lower_bound 구현하기

lower_bound는 어떤 수보다 크거나 같은 수가 처음 나오는 위치를 의미한다. 반대로, upper_bound는 어떤 수보다 큰 수가 처음 나오는 위치를 의미한다.

vector<int> v = {0, 1, 2, 3, 4, 5}; 
int target = 3; 

int left = 0, right = v.size() -1 ; 
while(left <= right){
    int mid = (left + right) / 2; 
    if(mid < target)
        left = mid + 1;
    else  // 값이 같은 경우에, 더 작은 값을 탐색한다.
        right = mid - 1;
}

이 코드에서는 찾는 값이 나왔을 때 right를 mid 값의 왼쪽으로 이동하며 더 작은 값을 탐색하고 있다. 따라서, 찾고자 하는 수보다 작거나 같은 수를 찾음으로써 lower_bound라고 할 수 있다. 

 

즉, 이분탐색에서는 mid값이 찾는 값이 나왔을 때, right = mid - 1 즉, 왼쪽 범위를 탐색하면 lower_bound이고 left = mid + 1 즉, 오른쪽 범위를 탐색하면 upper_bound이다.