[c++] upper_bound, lower_bound
- 두 함수는 이진탐색으로 구현되어 있기때문에 오름차순 정렬된 상태에서 사용해야 한다.
- algorithm 헤더에 포함되어 있다.
- ⭐️ 반환형이 iterator 이므로 첫 번째 원소의 주소를 빼줘야 인덱스를 구할 수 있다.
ex) lower_bound(v.begin(), v.end(), value) - v.begin() - 시간복잡도 : O(logn)
lower_bound
- 지정 범위에서 찾으려는 값보다 같거나 큰(이상) 첫 번째 원소의 위치 탐색
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
upper_bound
- 지정 범위에서 찾으려는 값을 초과하는 첫 번째 원소의 위치 탐색
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);
ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
💡 사용
- 특정 범위에 속하는 숫자의 갯수를 찾아야할 때
- 특정 숫자가 몇 번 나오는지 찾아야할 때
Author And Source
이 문제에 관하여([c++] upper_bound, lower_bound), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minwest/cpp-upperbound-lowerbound저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)