[c++] upper_bound, lower_bound

2333 단어 cppcpp
  • 두 함수는 이진탐색으로 구현되어 있기때문에 오름차순 정렬된 상태에서 사용해야 한다.
  • 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 );

💡 사용

  • 특정 범위에 속하는 숫자의 갯수를 찾아야할 때
  • 특정 숫자가 몇 번 나오는지 찾아야할 때

좋은 웹페이지 즐겨찾기