upper_bound, lower_bound

둘 다 이진탐색 (Binary Search) 기반의 탐색법이다.

이진탐색 (Binary Search) 기반이므로 배열이나 리스트가 오름차순으로 정렬되어있어야 한다.

 

[upper_bound]

upper_bound는 key 값을 초과하는 가장 첫 번째 원소의 위치 (주소)를 구한다.

사용법 : upper_bound(시작 주소, 끝 주소, key 값)

리스트의 값이 key 값을 가장 먼저 초과하는 주소 값을 리턴한다.

찾는 값이 없을 경우 끝 주소를 리턴한다. (벡터의 경우 , v.end() )

 

v : 1, 1, 2, 2, 3, 3, 4, 4
upper_bound(v.begin(), v.end(), 3)
=> v[6] 의 주소값을 리턴한다.

---

[lower_bound]

lower_bound는 key와 같거나 큰 가장 첫 번째 원소의 위치를 구한다.

사용법 : lower_bound(시작 주소, 끝 주소, key 값)

리스트의 값이 key 과 같거나 큰 최초 주소값을 리턴

찾는 값이 없을 경우, 끝 주소를 리턴한다. (벡터의 경우, v.end() )

---

[lower / upper 에서 인덱스 찾기]

lower / uppser bound는 주소값을 리턴하는데, 인덱스를 찾고싶으면 어떡할까?

sol ) lower_bound (시작주소, 끝주소, key 값) - 시작 주소

ex) lower_bound(v.begin(), v.end(), key) - v.begin() == 내가 찾은 값에 해당하는 벡터 내부의 인덱스