[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 );

💡 사용

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