lower_bound, upper_bound 이용 방법

algorithm 헤더에 존재하는

lower_bound와 upper_bound는 다음과 같은 의미를 가진다.

lower_bound(first iterator, last iterator, value)

 

vector를 기준으로 설명한다면 벡터의 첫 이터레이터(vector.begin()) 그리고 

벡터의 마지막 이터레이터(vector.end())를 의미하고 value는 찾고자 하는 값을 의미한다.

시작 이터레이터 ~ 끝 이터레이터 사이에서 value 이상인 값을 가지는 이터레이터를 반환하게 된다.

이 과정은 Binary Search로 이루어지기 때문에 항상 lower_bound를 동작시키기 위해서는 해당하는 벡터는 정렬되어 있어야 한다.

이때 이터레이터를 반환받지 않고 인덱스를 반환 받기 위해서는

lower_bound( ~ ) - vector.begin()을 하게 된다면 인덱스를 반환 받을 수 있다.

upper_bound(first iterator, last iterator, value)

 

vector를 기준으로 설명한다면 벡터의 첫 이터레이터(vector.begin()) 그리고 

벡터의 마지막 이터레이터(vector.end())를 의미하고 value는 찾고자 하는 값을 의미한다.

시작 이터레이터 ~ 끝 이터레이터 사이에서 value 보다 큰 값(초과 값)을 가지는 이터레이터를 반환하게 된다.

이 과정은 Binary Search로 이루어지기 때문에 항상 upper_bound를 동작시키기 위해서는 해당하는 벡터는 정렬되어 있어야 한다.

이때 이터레이터를 반환받지 않고 인덱스를 반환 받기 위해서는

upper_bound( ~ ) - vector.begin()을 하게 된다면 인덱스를 반환 받을 수 있다.

즉, lower_bound, upper_bound 모두 바이너리 서치를 통해 값을 찾아주는 역할을 하지만,

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

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

소스 코드 : 

// lower_bound / upper_bound example
#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;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>