[알고리즘] Lower Bound와 Upper Bound

✏️ 무엇인가? Lower Bound와 Upper Bound는 모두 경계값을 찾는 과정이다. 이진탐색(Binary Search)가 '원하는 값을 찾는 과정' 이었다면 Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고, Upper Bound는 '원하는 값이 나오는 마지막 위치를 찾는 과정'이다. Array = [1, 1, 2, 2, 3, 4, 4, 4, 6] 이런 리스트가 있에서 Lower Bound로 4를 찾는다면 4가 처음 나오는 인덱스인 5가 Output이 될 것이고, Upper Bound로 찾는다면 4가 마지막으로 나오는 인덱스인 7이 Output이 될 것이다. ✏️ 구현과정의 고민 사실 선형 탐색으로 구현하면 바로 해결되지만 기왕이면 O(N)보다는 O(lgN)이 좋지 않겠나..