이분 탐색

lower bound

[s, e] 구간에 속한 원소 중 어떤 성질이 성립하는 가장 작은 원소를 $hi$에 담는다.

구간 내의 어떤 지점에서도 성질이 성립하지 않으면 $hi = e+1$이다.

// lower bound
int lo = s-1, hi = e+1;         // 1
while (lo + 1 < hi) {           // 2
    int mid = (lo + hi) / 2;    // 3
    if (ok(mid)) hi = mid;      // 4
    else lo = mid;
}
 

 

1) $lo = s-1$, $hi = e+1$에서 시작한다.

3) 반복 조건이 $lo + 1 \lt hi$이므로 반복문 내에서 $lo$와 $hi$가 2 이상 차이난다.

   $hi = lo + d$  ($d\ge 2$)

   $lo + hi = lo\times 2 + d$

   $mid = \lfloor\frac{lo\times 2 + d}{2}\rfloor = lo + \lfloor\frac{d}{2}\rfloor$   $(1\le \lfloor\frac{d}{2}\rfloor\lt d)$

   $\therefore lo \lt mid \lt hi $

   $mid$가 구간을 벗어나지 않는다.

4) 반복문 종료 시 $hi$에 정답이 담겨 있어야 하므로

   $mid$에서 성질이 성립하면 hi = mid;

   $mid$에서 성질이 성립하지 않으면 lo = mid;

2) 반복문 종료 시 $lo + 1 \ge hi$이고, 3)과 4)에 의해 $lo \lt hi$이므로 $hi = lo + 1$이다.

 

 

upper bound

[s, e] 구간에 속한 원소 중 어떤 성질이 성립하는 가장 큰 원소를 $lo$에 담는다.

구간 내의 어떤 지점에서도 성질이 성립하지 않으면 $lo = s-1$이다.

// upper bound
int lo = s-1, hi = e+1;         // 1
while (lo + 1 < hi) {           // 2
    int mid = (lo + hi) / 2;    // 3
    if (ok(mid)) lo = mid;      // 4
    else hi = mid;
}