upper_bound
upper_bound (상한 경계 이진 탐색)
정렬된 범위에서 주어진 값보다 큰 첫 번째 원소를 찾는 알고리즘이에요. <algorithm> 헤더에 있어요.
출처: cppreference
본문
upper_bound는 정렬된 범위 [first, last)에서 value보다 큰 첫 원소를 찾아요.
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last,
const T& value ); // (1)
비교기 버전도 있어요.
template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last,
const T& value, Compare comp ); // (2)
- 반환 값:
value보다 큰 첫 원소 반복자. 없으면last. - 복잡도: 로그적.
std::vector<int> v{1, 2, 2, 4, 5};
auto it = std::upper_bound(v.begin(), v.end(), 2);
// 첫 4를 가리킴
lower_bound는 "크거나 같은" 첫 위치, upper_bound는 "보다 큰" 첫 위치예요. 둘의 차이로 같은 값의 구간을 계산할 수 있어요.