lower_bound, upper_bound

lower_bound & upper_bound

std::lower_bound - cppreference.com

std::upper_bound - cppreference.com

---

   Definition   

• lower_bound : 찾고자 하는 값 이상의 수가 처음으로 나오는 곳의 index를 구할때 사용
• upper_bound : 찾고자 하는 값보다 큰 수가 처음으로 나오는 곳의 index를 구할때 사용

---

   How to use   

Binary search를 기반으로 탐색되므로, 탐색되는 vector 혹은 list 는 sort 되어있어야 한다.

  lower_bound, upper_bound는 구하고자 하는 곳의 iterator를 return 한다. 따라서 실제로 사용할 경우 구한 lower_bound 혹은 upper_bound 값에서 vector array의 first iterator를 빼주어야 구하고자 하는 곳의 index값을 얻을 수 있다. 아래와 같이 사용하면 된다.

 

• vector<int> vec;
• lower_bound (vec.begin(), vec.end(), value) - vec.begin();
• upper_bound (vec.begin(), vec.end(), value) - vec.begin();

 

• int arr[N];
• lower_bound (arr, arr + N, value) - arr + 1;
• upper_bound (arr, arr + N, value) - arr + 1;

---

   Example   

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() {
    vector<int> vec(5);
    int arr[5];
 
    vec[0] = arr[0] = 5;
    vec[1] = arr[1] = 2;
    vec[2] = arr[2] = 2;
    vec[3] = arr[3] = 3;
    vec[4] = arr[4] = 5;
 
    sort(vec.begin(), vec.end());
    sort(arr, arr + 5);
 
    // sorted form : 2 2 3 5 5
 
    cout << " vec lower_bound(3) : "
        << lower_bound(vec.begin(), vec.end(), 3) - vec.begin() << '\n';
    cout << " arr lower_bound(3) : "
        << lower_bound(arr, arr + 5, 3) - arr << '\n';
    cout << " vec upper_bound(3) : "
        << upper_bound(vec.begin(), vec.end(), 3) - vec.begin() << '\n';
    cout << " arr upper_bound(3) : "
        << upper_bound(arr, arr + 5, 3) - arr << '\n' << '\n';
    cout << " vec lower_bound(5) : "
        << lower_bound(vec.begin(), vec.end(), 5) - vec.begin() << '\n';
    cout << " arr lower_bound(5) : "
        << lower_bound(arr, arr + 5, 5) - arr << '\n';
    cout << " vec upper_bound(5) : "
        << upper_bound(vec.begin(), vec.end(), 5) - vec.begin() << '\n';
    cout << " arr upper_bound(5) : "
        << upper_bound(arr, arr + 5, 5) - arr << '\n';
}

  위 코드의 실행 결과는 아래와 같다.

실행 결과

  upper_bound(5)의 경우 5를 초과하는 첫번째 숫자의 index를 구하는 것인데 주어진 vector, array 안에는 5를 초과하는 수가 없으므로 주어진 vector, array 의 last index 에 (+1)한 값이 return 된다.

 

  만약, 위 벡터에서 lower_bound(4) 를 하면 4에 해당하는 index 값이 없으므로, upper_bound(4)와 같은 결과를 낸다.