220117 이분탐색 : UpperBound vs LowerBound

Lower bound 는 타겟보다 같거나 큰 값이 처음 나오는 위치

Upper bound 는 타겟보다 처음으로 큰값이 나오는 위치

 

 

이진 탐색에서 Pivot == Target 인 경우 return 하는데

이것을 LowerBound, UpperBound 를 찾는 경우에는 Pivot == Target 일 때 low 나 high 를 조절해서 적절한 위치를 찾아주어야 한다.