[C++] lower_bound, upper_bound

 

* 사용전 오름차순 정렬 필수

 

[ lower_bound ]

찾으려는 값보다 같거나 큰 숫자가 배열의 몇 번째에서 처음 등장하는지 이분 탐색.

 

[ upper_bound ]

찾으려는 값을 초과하는 숫자가 배열의 몇 번째에서 처음 등장하는지 이분 탐색.

 

이분 탐색이므로 둘 다 O(log N).

vector<int> v;

/* ... */

::sort(v.begin(), v.end());

const int lowerCnt = (::lower_bound(v.begin(), v.end(), 3) - v.begin());

const int upperCnt = (::upper_bound(v.begin(), v.end(), 3) - v.begin());

 

 

[ 연습 문제 ]

lower_bound과 upper_bound를 같이 사용하는 풀이 존재.

https://www.acmicpc.net/problem/3020