이분 탐색은 찾고자 하는 값이 없으면 탐색에 실패한다.
이를 해결하기 위해 찾고자 하는 값이 존재하지 않을 수도 있는 경우를 처리하기 위해 Upper Bound와 Lower Bound가 사용된다.
Upper Bound는 찾고자 하는 값보다 큰 값이 처음 나타나는 위치를 반환한다.
Lower Bound는 찾고자 하는 값 이상이 처음 나타나는 위치를 반환한다.
두 개념 모두 이분 탐색의 조건을 조금 변경하면 된다.
이분 탐색과의 차이점
이분 탐색과 Upper/Lower Bound에는 구간 정의의 차이가 있다.
이분 탐색의 구간 정의는 start <= end이 반면 Upper/Lower Bound는 start < end이다.
즉, 이분 탐색은 start > end일 때 멈추고 Upper/Lower Bound는 start == end일 때 멈춘다.
왜냐하면 Upper/Lower Bound는 조건을 만족하는 최솟값 위치를 찾는 것이 목적이다.
즉, 정확한 값을 찾는 게 아니라 경계를 찾는 것이다.
따라서 값을 찾았다고 해도 멈추지 않고 더 왼쪽/오른쪽으로 이동하며 start == end가 되면, 그 위치가 곧 원하는 경계선이다.
반면 이분 탐색은 정확한 값을 찾는 것이 목적이다.
중간값이 목표한 값이면 바로 반환하고 그렇지 않으면 왼쪽/오른쪽 절반을 완전히 버리기 위해 구간을 한 칸씩 줄여 나간다.
start > end가 되면 탐색할 범위가 없다는 뜻이다.