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