컴퓨터공학/자료구조 및 알고리즘 이론
[C++] lower_bound, upper_bound
Pyxis
2024. 10. 21. 17:45
* 사용전 오름차순 정렬 필수
[ 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를 같이 사용하는 풀이 존재.