STL lower_bound, upper_bound

직관적이지 않은 동작이 있는데, 아래 예제를 통해 파악해보자.

{    //찾으려는 값이 있는 경우,
    //lower_bound는 가장 왼쪽 위치를
    //upper_bound는 가장 오른쪽 보다 한칸 오른쪽 위치를 리턴(주의)
    int arr[] = { 1,2,3,4,5,5,5,6 };
    auto l = lower_bound(arr, arr + 8, 5);
    auto r = upper_bound(arr, arr + 8, 5);
    printf("l:%d, r:%d, *l:%d, *r:%d\n", l - arr, r - arr, *l, *r);
}
{    //찾으려는 값이 없는 경우,
    //lower_bound는 한칸 오른쪽 위치를,
    //upper_bound도 마찬가지로 한칸 오른쪽 위치를 리턴(이경우 두 값이 같음)
    int arr[] = { 1,2,3,4,6 };
    auto l = lower_bound(arr, arr + 5, 5);
    auto r = upper_bound(arr, arr + 5, 5);
    printf("l:%d, r:%d, *l:%d, *r:%d\n", l - arr, r - arr, *l, *r);
}

출력:

l:4, r:7, *l:5, *r:6
l:4, r:4, *l:6, *r:6  

 

찾으려는 값이 왼쪽에 더 가까워도, 한칸 오른쪽 위치를 리턴함에 주의하자.

vector<int> v = { 1,5,10,15,20 };
auto l = lower_bound(v.begin(), v.end(), 11);
auto r = upper_bound(v.begin(), v.end(), 11);
printf("l:%d, r:%d, *l:%d, *r:%d\n", l - v.begin(), r - v.begin(), *l, *r);

출력: (15보다는 10에 가까운 11을 찾았음에도, 15의 인덱스 위치를 리턴함에 주의)

l:3, r:3, *l:15, *r:15