lower_bound, upper_bound 의 차이

lower_bound 와 upper_bound 모두 정렬되어진 컨테이너에서 원하는 값을 찾는것이다. 즉 먼저 정렬이 되어있다는것이 기본이다. 이 두함수는 비슷한듯 차이가 있는데 

1. lower_bound

 - 반환값이 이터레이터이므로 원하는 index를 반환받기 위해서는 distance(v.begin(), lower_bound())를 통해 인덱스를 반환

2. upperr_bound

 - 반환값이 이터레이터이므로 원하는 index를 반환받기 위해서는 distance(v.begin(), upper_bound())를 통해 인덱스를 반환

이 둘의 차이점은 바로 둘다 binary search를 통해서 값을 찾아주기는 하지만

lower_bound는 value를 포함한 이상인 값을 , upper_bound는 value를 포함하지 않은 초과인 값을 찾아내준다. 

#include <iostream>
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>
 
int main() 
{
    int arr[] = { 10,20,30,30,20,10,10,20 };
    vector<int> vc(arr, arr + 8);  // 10 20 30 30 20 10 10 20
 
    sort(vc.begin(), vc.end()); // 10 10 10 20 20 20 30 30
 
    vector<int>::iterator low, up;
    low = lower_bound(vc.begin(), vc.end(), 20); // vc에서 20 이상인 수의 이터레이터를 찾는다.
    up = upper_bound(vc.begin(), vc.end(), 20); // vc에서 20 초과인 수의 이터레이터를 찾는다.
 
    cout << "lower_bound at position " << (low - vc.begin()) << '\n';
    cout << "upper_bound at position " << (up - vc.begin()) << '\n';
 
    /*
    Output
    lower_bound at position 3
    upper_bound at position 6
    */
 
    return 0;
}
 
 
출처: http://www.crocus.co.kr/913 [Crocus]

아래 코드를 통해 예시를 살펴보자.

벡터에 10, 20, 30, 30, 20, 10, 10, 20이라는 값을 받게 되고 정렬을 통해 10 10 10 20 20 20 30 30으로 만들어준다.

여기서 lower_bound(vc.begin(), vc.end(), 20)을 하게되면 20 이상인 이터레이터를 반환하는데 거기서 -vc.begin()을 하게 되면

인덱스인 3을 반환하게 된다.

upper_bound는 20 초과인 값을 반환나게 되니 결국 6을 반환하게 된다는 의미이다.

해당 포스팅은 http://www.crocus.co.kr/913 를 기반으로 작성하였습니다