TL;DR

• 정렬된 리스트 보다는 주어진 검색결과 (혹은 함숫값)가 True, False 구간으로 나뉘어있을 때 그 경계를 찾는 문제라고 보는 게 더 낫다.

• 그러면 lower_bound 문제는 $v \ge x$ 를 만족하는 첫번째 v를 찾는 문제가 되고

• upper_bound 문제는 $v \gt x$를 만족하는 첫번째 v를 찾는 문제가 된다.

• 아래 표는 어떤 정렬된 배열에서 x = 20에 대한 lower_bound와 upper_bound를 찾은 모습이다.

  10	20	20	20	30	40
  	lower_bound			upper_bound

구현방법

실수의 여지가 오지게 많다. 꼼꼼하게 살펴볼 필요가 있다. 실수를 줄이기 위해서 다음과 같은 마인드로 구현해보자.

• IF 문은 한 번만 쓰는 게 좋다. v < x, v == x, v > x 이따위로 조건문 세개로 나누는 건 이분탐색에 어울리지 않아!
• 중간값(m)에 대한 함숫값이 참인 경우 ⇒ [m, r) 범위는 볼 필요가 없다. 따라서 [l, m) 범위를 탐색하면 된다.
• 중간값 m에 대한 함숫값이 거짓인 경우 ⇒ [l, m+1) 범위는 볼 필요가 없다. 따라서 [m+1, r) 범위를 탐색하면 된다.

이런 식으로 소거법으로 정리해 나간다는 느낌으로 코드를 짜면 언제 반복문을 나가야 할지, 언제 l,r을 바꿔야 할지 알 수 있다.

pseudo code

def first_true(begin, end, pred):
	l = begin
	r = end
	while l != r :
		m = l + (r - l) / 2 # overflow 방지
		match pred(m):
			case True:
				r = m 
			case _:
				l = m + 1
	return l

/**
F-...-F-F-F-T-T-T-...-T
            ^
*/
template <typename T, class Predicate>
inline T first_true(T begin, T end, Predicate const &pred) {

  T l = begin;
  T r = end;
  while (l < r) {
    T mid = l + (r - l) / 2;
    if (pred(mid)) {
      // next range is [l, mid)
      r = mid;
    } else {
      // next range is [mid + 1, r)
      l = mid + 1;
    }
  }
  return l;
}

first_true로 구현한 upper_bound

TEST(BinSearch, UpperBound) {
  vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
  int key = 5;
  auto upper_b = first_true(sorted.begin(), sorted.end(),
                            [key](auto e) { return key < *e; });
  auto real_upper_b = std::upper_bound(sorted.begin(), sorted.end(), key);
  ASSERT_EQ(real_upper_b, upper_b);
}

first_true로 구현한 lower_bound

TEST(BinSearch, LowerBound) {
  vector<int> sorted = {1, 3, 5, 5, 5, 7, 9};
  int key = 5;
  auto lower_b = first_true(sorted.begin(), sorted.end(),
                            [key](auto e) { return key <= *e; });
  auto real_lower_b = std::lower_bound(sorted.begin(), sorted.end(), key);
  ASSERT_EQ(real_lower_b, lower_b);
}

Parametric Search로의 확장

이진탐색은 최적화 문제를 결정 문제로 바꿔서 풀 수 있게 해준다.