[C++] lower_bound, upper_bound 사용해보기

lower_bound, upper_bound

▶ lower_bound(start, end, val) =  [start, end) 범위에서 val 이상인 첫 번째 원소 위치 반환

▶ upper_bound(start, end, val) =  [start, end) 범위에서 val 을 초과하는 첫번째 원소 위치 반환

Harbang lower_bound(Harbang first, Harbang last, const T& value);
Harbang lower_bound(Harbang first, Harbang last, const T& value, Compare comp);

Harbang upper_bound(Harbang first, Harbang last, const T& value);
Harbang upper_bound(Harbang first, Harbang last, const T& value, Compare comp);

 

-  4번째 인자로 Comparator가 들어갈 수 있다.

-  #include <algorithm>

-  lower_bound와 upper_bound는 내부적으로 이진 탐색을 수행하기 때문에

　범위 내의 원소들이 비내림차순으로 정렬되어 있어야 한다. 

 

[예제]

vector<int> v = { -2, -2, -1, -1, 0, 0, 0, 1, 1 };

cout << lower_bound(v.begin(), v.end(), 0) - v.begin() << '\n';  // 4

cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << '\n';  // 7

 

 

ower_bound(0)에서 0 이상인 값이

처음으로 나오는 인덱스 4 반환

 

upper_bound(0)에서는 0을 초과하는 값이

처음 나오는 인덱스 7 반환

 

 

Reference

- Binary Search (이분 탐색)

Binary Search (이분 탐색)

 

 

- Parametric Search

[탐색] Parametric Search

 

 

- 정렬 알고리즘 비교

정렬 알고리즘 비교