[C++] STL lower_bound와 upper_bound 함수 사용법

lower_bound와 upper_bound

lower_bound와 upper_bound 함수를 사용하기 위해선 먼저 헤더 파일을 포함해야 합니다.

#include <algorithm>

 

lower_bound 함수는 지정된 범위에 있는 요소들 중에서 주어진 값보다 같거나 큰, 첫 번째 요소의 위치를 반환하는 함수입니다.

 

이 함수 정의는 다음과 같습니다.

template<class ForwardIterator, class Type>
ForwardIterator lower_bound(
    ForwardIterator first,
    ForwardIterator last,
    const Type& value );

양방향 반복자( bidirectional iterator )와 임의 접근 반복자( random access iterator )도, 순방향 반복자( forward iterator )를 포함하므로, 이 함수를 호출하는 데 사용할 수 있습니다.

 

STL 반복자( iterator )에 관한 내용을 보고 싶다면, 여기에서 볼 수 있습니다.

[C++] 반복자( Iterator )에 대한 설명과 종류

 

upper_bound 함수는 지정된 범위에 있는 요소들 중에서 주어진 값보다 큰, 첫 번째 요소의 위치를 반환하는 함수입니다.

함수 정의는 lower_bound와 같으므로 생략하겠습니다.

 

이 함수들은 요소를 탐색하는데, 이진 탐색( binary search ) 방식을 사용하기 때문에, 제대로 동작하려면 탐색하는 데이터가 이미 정렬되어 있어야 합니다.

 

다음은, 기본적인 int 배열에서 주어진 요소를 탐색하는 예제입니다.

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

int main(){

    int arr[] = { 1, 2, 3, 4, 5 };

    int* pLower = lower_bound(arr, arr+5, 4);

    int* pUpper = upper_bound(arr, arr+5, 4);

    cout << "Lower: " << *pLower << endl;
    cout << "Upper: " << *pUpper << endl;
    
    return 0;
}

▼출력

Lower: 4
Upper: 5

lower_bound는 4와 같거나 큰 멤버를 가리키는 위치를 반환하므로, 멤버 4를 가리키는 위치를 반환하고,

upper_bound는 4보다 큰 멤버를 가리키는 위치를 반환하므로, 멤버 5를 가리키는 위치는 반환합니다.

 

lower_bound와 upper_bound의 관계

이번엔, vector 컨테이너에서 원하는 요소를 탐색하는 예제입니다.

int main(){

    vector<int> arr = { 1, 2, 3, 4, 5, 5, 5, 5, 6, 7};

    auto iLower = lower_bound( arr.begin(), arr.end(), 5);

    auto iUpper = upper_bound( arr.begin(), arr.end(), 5);

    cout << "Lower: " << *iLower << endl;
    cout << "Upper: " << *iUpper << endl;

    int cnt = iUpper - iLower;  // iUpper와 iLower 위치사이의 원소 개수
    cout << "count of 5: " << cnt;

    return 0;
}

▼출력

Lower: 5
Upper: 6
count of 5: 4

 

이 예제를 이미지로 표현하면 다음과 같습니다.

 

lower_bound와 upper_bound의 관계

 

이 이미지를 보면,

원소 5가 시작되고 끝나는 구간을, 이 함수들을 통하여 알 수 있고, 함수 이름을 이렇게 지은 이유도 알 수 있습니다.

 

그리고, 두 함수에서 반환한 반복자( iterator )의 '-' 연산자를 통해, 두 반복자 사이의 요소 개수를 알 수도 있습니다.

이를 통해서, 이 vector가 가지고 있는 요소 5의 개수를 구할 수 있습니다.

참고로, 연산자 '-'를 지원하는 반복자는 임의 접근 반복자뿐입니다.

 

만약, 찾은 원소의 인덱스를 알고 싶다면 다음과 같이 할 수도 있습니다.

int main(){

    vector<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8 };

    int idx = lower_bound( arr.begin(), arr.end(), 5) - arr.begin();
    
    cout << "index of 5: " << idx;

    return 0;
}

▼출력

index of 5: 4

 

만약, 주어진 값을 찾을 수 없으면 어떻게 될까요?

lower_bound와 upper_bound가 찾는 값이 검색하는 모든 데이터보다 커서 컨테이너 안에 없으면, end() 위치를 반환합니다.

반대로, 모든 데이터보다 작은 경우, begin() 위치를 반환합니다.

 

int main(){

    vector<int> arr = { 1, 2, 3, 4, 5, 6, 7, 8 };

    vector<int>::iterator iter = upper_bound( arr.begin(), arr.end(), 8);
    
    bool bEnd = (iter == arr.end()) ? true : false;
    cout << "upper end: " << bEnd << endl;

    iter = lower_bound( arr.begin(), arr.end(), 0);

    bEnd = (iter == arr.begin()) ? true : false;
    cout << "lower end: " << bEnd;

    return 0;
}

▼출력

upper end: 1
lower end: 1

 

내림차순 탐색

이 함수의 다른 버전도 있습니다.

template<class ForwardIterator, class Type, class BinaryPredicate>
ForwardIterator lower_bound(
    ForwardIterator first,
    ForwardIterator last,
    const Type& value,
    BinaryPredicate pred );

인자인 pred는 한 요소가 다른 요소보다 작다는 의미를 정의하는 사용자 정의 이진 조건자입니다.

여기서, 이진 조건자는 두 개의 인수를 사용하여 조건이 충족되면 true를 반환하고, 충족되지 않으면 false를 반환하는 함수 객체를 말합니다.

 

이러한 이진 조건자의 예로, greater <T> 함수 객체를 들 수 있습니다.

이 함수는 첫 번째 인자가 두 번째 인자보다, 더 크면 true를 반환합니다.

 

따라서, 정렬 sort 함수를 쓸 때, 이 함수 객체를 사용하면 내림차순으로 정렬됩니다.

좀 더, 자세히 알고 싶다면, 여기에서 보실 수 있습니다.

[C++] STL sort 함수 사용법

 

이 함수 객체를 사용하면, 

lower_bound는 주어진 값보다 같거나 작은, 첫 번째 요소의 주소를 반환합니다.

그리고, upper_bound는 주어진 값보다 작은, 첫 번째 요소의 주소를 반환합니다.

 

하지만, 주어진 데이터가 내림차순으로 정렬이 되어 있어야 함수가 제대로 동작한다는 것을 주의해야 합니다.

int main(){

    vector<int> arr = { 1, 2, 3, 4, 5, 5, 5, 5, 6, 7};

    // 내림차순 정렬이 필요.
    sort( arr.begin(), arr.end(), greater<int>());

    auto iLower = lower_bound( arr.begin(), arr.end(), 5, greater<int>());

    auto iUpper = upper_bound( arr.begin(), arr.end(), 5, greater<int>());

    cout << "Lower: " << *iLower << endl;
    cout << "Upper: " << *iUpper << endl;

    int cnt = iUpper - iLower;  // iUpper와 iLower 위치사이의 원소 개수
    cout << "count of 5: " << cnt;

    return 0;
}

▼출력

Lower: 5
Upper: 4
count of 5: 4

 

내림차순으로 탐색