C++ lower_bound와 upper_bound

이진탐색(Binary Search)기반의 탐색 방법: 배열 또는 리스트가 정렬되어있어야함

 

- lower_bound: 찾으려는 key보다 같거나 큰 숫자가 처음 등장하는 위치

- upper_bound: 찾으려는 key 값을 초과하는 숫자가 처음 등장하는 위치

 

pair로 된 vector에 대해 lower_bound, upper_bound를 사용할 때는 찾고자 하는 key에만 값을 넣고, 탐색할 필요 없는 쌍은0으로 넣어준다

auto it = lower_bound(arr.begin(), arr.end(), pii(0, b - 2), comp) - arr.begin();