algorithm_upper_bound
algorithm_upper_bound (상한 탐색)
std::upper_bound는 파티셔닝된 정렬 범위에서 value보다 뒤서는 첫 번째 요소를 찾아요. value보다 큰 요소들이 시작되는 위치를 돌려줘요.
출처: cppreference
본문
std::upper_bound는 파티셔닝된 소스 범위 [first, last)에서 value보다 뒤서는(즉 value가 그 요소보다 앞서는) 첫 번째 요소를 찾아요. <algorithm> 헤더에 정의되어 있어요.
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 );
- 1번 오버로드 — 순서는
operator<(즉std::less{})로 결정돼요. 요소들이bool(value < e)에 대해 파티셔닝되어 있어야 해요. - 2번 오버로드 — 순서는 비교 함수
comp로 결정돼요.
반환값 (Return value)
value보다 뒤서는 첫 번째 요소를 가리키는 반복자예요. 그런 요소가 없으면 last를 돌려줘요.
복잡도 (Complexity)
N을 std::distance(first, last)라고 하면 log₂(N) + 𝓞(1)번 이하의 비교가 필요해요.
예제 (Example)
#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
std::vector<int> data{1, 2, 4, 4, 5, 6, 7};
for (int v : {4, 8})
{
auto it = std::upper_bound(data.begin(), data.end(), v);
std::cout << "upper_bound(" << v << ") = " << std::distance(data.begin(), it) << '\n';
}
}
출력:
upper_bound(4) = 4
upper_bound(8) = 7