[C++] upper_bound()와 lower_bound()

<algorithm> 라이브러리에 정의.

 /* lower_bound */
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );

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

/* upper_bound */
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

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

lower_bound() 는 vector와 같이 Random Access가 가능한 자료구조의 Iterator를 활용하여,

3rd 인자로 주어진 value보다 크거나 같은 값이 나오는 첫 인덱스를 반환해주는 함수이다.

lower_bound()를 이용하면 코드 안에 반복문과 조건문을 넣지 않고도 빠르게 원하는 위치의 Iterator를 얻을 수 있다.

lower_bound와 upper_bound를 사용할 때 주의할 점은 first와 last 범위 안에 있는 원소들이 정렬되어 있는 상태여야 한다.

 

comp를 작성하여 인자로 넘겨주지 않으면 기본적으로 lower_bound는 원소가 value보다 크거나 같은지 검사하여, 참이면 리턴하고 upper_bound는 원소가 value보다 큰지 검사하여, 참이면 리턴한다.

 

Argument (인자)

• first, last: 원소들의 범위를 나타내는 Iterator.
  • first는 범위의 첫번째 원소를, last는 범위의 마지막 원소 바로 다음을 가리킨다.
• value: 자료구조 안의 원소들과 비교할 값.
• comp: 주어질 경우, 이 비교함수에 맞추어 결과를 리턴한다.

Time Complexity (시간 복잡도)

• $ range = first - last $ 일 때, 시간 복잡도는 $ O(log_2(range)) $ 이다.

사용 예시

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> v = {1, 2, 3, 5, 6, 9};

    auto lower = lower_bound(v.begin(), v.end(), 3);
    auto upper = upper_bound(v.begin(), v.end(), 6);

    cout << "[lower_bound]\n" 
         << "index: " << (lower - v.begin()) << endl
         << "value: " << *lower << endl << endl;
    cout << "[upper_bound]\n" 
         << "index: " << (upper - v.begin()) << endl
         << "value: " << *upper << endl << endl;
    return 0;
}

[출력]

[lower_bound]
index: 2
value: 3

[upper_bound]
index: 5
value: 9