[C++] upper_bound, lower_bound

upper_bound

 

https://www.cplusplus.com/reference/algorithm/upper_bound/?kw=upper_bound 

upper_bound - C++ Reference

배열 (vector)에서 key 값을 초과하는 숫자가 몇 번째로 등장하는 지를 찾아준다. "초과"하는 숫자를 찾기 때문에 반환된 iterator가 가리키는 값이 key값이 아니다. (lower_bound와 다른 점)

전제조건은 배열이 오름차순으로 정렬되어 있어야 한다는 것이다.

 

1. default

template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

 

2. custom

template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){

    vector<int> v = {3, 7, 8, 9, 1, 2, 4};
    sort(v.begin(), v.end());
    cout << upper_bound(v.begin(), v.end(), 4) - v.begin();
}

벡터 v 가 정렬되면 {1, 2, 3, 4, 7, 8, 9}가 될 것이고, key값인 4가 처음 등장하는 곳, 즉 v[3]의 주소를 반환할 것이다.

 

이 함수는 iterator을 반환하기 때문에 int 형식의 index를 찾고 싶다면 저렇게 벡터의 시작 주소를 빼줘야 한다. 

 

lower_bound

https://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound 

lower_bound - C++ Reference

벡터를 탐색하면서 key값 보다 작지 않은 값이 처음으로 나오는 요소의 iterator를 반환한다 

역시 벡터가 정렬되어 있어야 한다. 

 

1. default

template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

 

2. custom

template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

 

사용 방식은 upper_bound와 동일하다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){

    vector<int> v = {3, 7, 8, 9, 1, 2, 4};
    sort(v.begin(), v.end());
    cout << lower_bound(v.begin(), v.end(), 4) - v.begin();
}

벡터 v 가 정렬되면 {1, 2, 3, 4, 7, 8, 9}가 될 것이고, key값인 4가 처음 등장하는 곳, 즉 v[3]의 주소를 반환할 것이다.

역시 인덱스를 얻고 싶다면 벡터의 시작 주소를 뺴줘야 한다.