[Algorithm] Lower Bound & Upper Bound 정리

Lower Bound & Upper Bound 란?

Lower(Upper) Bound는 원하는 값이 처음 나오는 위치를 찾는 알고리즘이다.
Lower Bound는 원하는 값 k 이상의 수가 처음으로 나오는 위치를 찾는다면,
Upper Bound는 원하는 값 k를 초과하는 수가 처음으로 나오는 위치를 찾는다.

📖 알고리즘 특징

- 이분 탐색 알고리즘(binary search algorithm)에서 파생됐다.
- 배열 안의 숫자들이 오름차순으로 정렬되어 있을 때 이용할 수 있다.

---

Lower Bound

Lower Bound 알고리즘은 원하는 값 k 이상의 수가 처음으로 나오는 위치를 찾는다.

Lower Bound 알고리즘 수행 과정
중간 지점 찾기 → 값 비교 → 확인

파악하고자 하는 구간의 시작 위치를 start, 끝 위치를 end, 중간 값을 mid라고 하고,

예제를 들어 이해하기 쉽게 설명해보려고 한다.

1. 중간 지점 찾기

const mid = Math.floor((start+end) / 2);

시작 지점과 끝 지점을 더한 후, 2를 나누어준 뒤 Math.floor() 메소드를 사용해 소수점을 버려준다.

2. 값 비교

배열의 중간 지점의 값과 우리가 찾고자 하는 k를 비교한다. 이때 나올 수 있는 경우의 수는 3가지이다.

1. 중간 지점의 값보다 k가 크다.
2. 중간 지점의 값과 k가 같다.
3. 중간 지점의 값보다 k가 작다.

1번의 경우라면 다행이다. 중간 지점의 값이 lowerBound 값이 될 수는 없기 때문이다.

예를 들어, 우리는 5를 찾으려하는데 중간 지점의 값이 3이라면 3이 lowerBound가 될 수는 없다.

---

Reference

• https://blog.naver.com/bestmaker0290/220820005454
• https://gywlsp.github.io/algorithm/2/