이분 탐색, 하한 / 상한 값 탐색

[1. 개요]

정렬 된 배열에 같은 값을 갖는 원소가 여러 개일 경우

단순한 이분 탐색은 찾고자 하는 값에 해당하는 인덱스 중 가장 앞서는 값을 준다고 보장 할 수 없다.

물론, C++ 기준 std::lower_bound, upper_bound 를 사용하면 가능하겠지만,

vector 사용 없이, 단순 배열을 대상으로 lower_bound, upper_bound 에 해당하는 기능 구현에 관한 내용을 정리한다.

---

[2. 하한 / 상한]

하한 값 : 대상 값보다 같거나 작은 값 중 가장 큰 값

상한 값 : 대상 값보다 큰 값 중 가장 작은 값

• 최소값, .... 하한 값 ≤ 대상 값... < 상한 값...... 최대 값

---

[3. 단순한 이진 탐색 시 문제점]

배열: {1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6} 에서

 

3 을 찾고자 할 때, 

중간 값(index: lo 와 hi 의 가운데) 을 기준으로 3 이 어느쪽에 오는지 확인하는데,

중간 값이 아래와 같을 시, 적절히 다음 작업을 진행하는데,

• 3 보다 크면, 하위 구간에서 
• 3 보다 작으면 상위 구간에서 
• 같으면 발견한 것

문제는 발견한 경우 이 index 가 항상 같은 값 중 정렬 상 가장 앞서는 인덱스가 아닐 수 있다는 것이다.

---

[4. 해결책]

이진 탐색 시, 찾고자 하는 값이 있는 인덱스를 발견 하였더라도 이진 탐색을 계속 진행하도록 한다.

이진 탐색을 계속 진행하면, 값을 찾는 범위가 점점 좁혀지기 때문이다.

 

값 비교시,

• 등호가 있으면, 하한 값을 찾는 것이고
• 등호가 없으면, 상한 값을 찾는 것이다.
• 코드 참조,

---

[5. 코드]