5.1.2 Exponential Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/*

Finds the first value where a monotone Boolean predicate becomes true when an upper bound is not
known in advance. Exponential search first grows the search range by powers of two until it brackets
the transition point, then finishes with ordinary binary search.

This is useful for answer-search problems over unbounded or very large integer domains.

Overflow warning: The predicate must become true before the exponentially growing probe overflows
`Int`; otherwise, add an explicit limit.

- `exponential_first_true(lo, pred)` returns the smallest integer `x` greater than or equal to `lo`
  such that `pred(x)` is true.

Time Complexity:
- O(log n) calls to `pred()` per call, where $n$ is the distance from `lo` to the first true value.

Space Complexity:
- O(1) auxiliary.

*/

#include <cstdint>

template<typename Int, typename Pred>
Int exponential_first_true(Int lo, Pred pred) {  // 000[1]11
  if (pred(lo)) {
    return lo;
  }
  Int step = 1;
  while (!pred(lo + step)) {
    step *= 2;
  }
  Int hi = lo + step;
  lo += step / 2;
  while (lo < hi) {
    Int mid = lo + (hi - lo) / 2;
    if (pred(mid)) {
      hi = mid;
    } else {
      lo = mid + 1;
    }
  }
  return lo;
}

/*** Example Usage ***/

#include <cassert>

int main() {
  auto at_least_1000 = [](int x) { return x >= 1000; };
  assert(exponential_first_true(1000, at_least_1000) == 1000);
  assert(exponential_first_true(0, at_least_1000) == 1000);
  assert(exponential_first_true(5, at_least_1000) == 1000);
  auto square_large_enough = [](int64_t x) { return x * x >= 123456789LL; };
  assert(exponential_first_true(0LL, square_large_enough) == 11112);
  return 0;
}