lower_bound와 upper_bound

algorithm에 포함되어 있는 lower_bound와 upper_bound 덕분에 앞으로 코딩이 조금 편해질 것 같은데,

이름 때문인지 약간 헷갈려서 정리하고 가는 것이 좋을 것 같다.

기본적인 사용법

int arr[size] = {...};
int* ptr = lower_bound(arr, arr + size, n);

여기서 n은 찾고자 하는 수이다

반환되는 값은 다음과 같다.

* lower_bound: n 이상의 수 중 가장 작은 것

* upper_bound: n 초과의 수 중 가장 작은 것

(정확히는 pointer나 iterator가 반환된다)

이렇게만 알아놓으면 헷갈릴 일은 없을 것 같다.

<예시>

int arr[2] = {3, 5};

일 때 i = 0 ~ 7에 대해 각각 함수가 반환하는 포인터가 가리키는 값은?

<답>

lower_bound:

0~3 -> 3 // 4~5 -> 5 // 6~ -> end

upper_bound:

0~2 -> 3 // 3~4 -> 5 // 5~ -> end

경계에서 미묘한 차이가 있다.