Lower Bound & Upper Bound

Lower Bound와 Upper Bound는 일종의 이분 탐색에서 파생된 것으로,

이분 탐색이 '원하는 값 k를 찾는 과정' 이라면

Lower Bound는 '원하는 값 k 이상이 처음 나오는 위치를 찾는 과정' 이며,

Upper Bound는 '원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정'이다.

 

Lower Bound와 Upper Bound는 헤더파일 <algorithm>에도 구현되어 있다.

std::lower_bound( [배열의 처음 값의 주소], [배열의 끝 값의 주소], 찾고자 하는 값(k), [정렬])

std::upper_bound( [배열의 처음 값의 주소], [배열의 끝 값의 주소], 찾고자 하는 값(k), [정렬])