[C++] lower_bound vs upper_bound

lower_bound와 upper_bound가 항상 헷갈려 정리한다.

두 함수 모두 STL의 algorithm헤더에 정의되어 있다.

두 함수의 사용법은 동일하다. lower_bound(시작 주소, 끝 주소 + 1, 찾을 수)를 하면 된다. upper_bound도 동일하다.

또한 이진탐색을 기반으로 구현된 함수이기 때문에 정렬된 배열에서만 올바른 작동을 한다.

리턴 값으로는 찾은 인덱스의 주소값 또는 iterator를 리턴한다. 그렇기 때문에 인덱스 값을 얻고 싶다면 시작주소값 또는 시작 iterator값을 빼줘야 한다.

lower_bound

얘는 원하는 값을 찾은 첫 번째 인덱스의 주소, iterator 리턴한다. 만약 원하는 값이 없다면 원하는 값보다 큰 첫번째 놈을 리턴한다.

upper_bound

얘는 원하는 값보다 큰 첫번째 인덱스의 주소, iterator를 리턴한다.

사용 예시

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
   int arr[7] = {1, 2, 3, 4, 5, 5, 7};
   cout << "lower_bound(5) : " << lower_bound(arr, arr + 7, 5) - arr << endl;
   cout << "lower_bound(6) : " << lower_bound(arr, arr + 7, 6) - arr << endl;
   cout << "upper_bound(5) : " << upper_bound(arr, arr + 7, 5) - arr << endl;
   cout << "upper_bound(6) : " << upper_bound(arr, arr + 7, 6) - arr << endl;
}

결과값