Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Binary search

When there is no upper bound

Lesson · 7 min read · Binary search · Searching a monotone condition

Double a guess until it passes, then search between the last two guesses. The cost depends on the size of the answer, not on a bound you do not have.

Doubling first

Sometimes the range has no known top: a sorted stream whose length you are not told, or "the smallest n such that …" where n could be anything. Guess 1, then 2, 4, 8, … until a guess passes. The answer then lies between the last failing guess and the first passing one, a range no wider than the answer itself.

Exponential search for the first value that passes

firstTrueUnbounded(test)

  1. If test(1) passes, return 1 (or check 0 first if 0 is a candidate).
  2. b = 1. While test(b) fails: b = 2b.
  3. The answer is in [b / 2 + 1, b]: b / 2 failed and b passed.
  4. Run the first-true search on that range and return its result.

An example

The smallest n with n³ ≥ 5,000. The doubling phase tests 1, 2, 4, 8, 16, 32: 1³ = 1, 2³ = 8, 4³ = 64, 8³ = 512, 16³ = 4,096 all fail, and 32³ = 32,768 passes. So the answer is in [17, 32], and an ordinary search finishes the job.

The second phase: a first-true search on the bracket the doubling found.

  1. Step 1 / 6
    lo 17hi 32
    lo17hi32

    After doubling: 16 failed and 32 passed, so the answer is in [17, 32].

  2. Step 2 / 6
    lo 17hi 32mid 24 ✓
    lo17mid24hi32

    24³ = 13,824 ≥ 5,000. 24 works, so the answer is 24 or smaller: hi = 24.

  3. Step 3 / 6
    lo 17hi 2432mid 20 ✓
    lo17mid20hi24

    20³ = 8,000 ≥ 5,000. 20 works, so the answer is 20 or smaller: hi = 20.

  4. Step 4 / 6
    lo 17hi 2032mid 18 ✓
    lo17mid18hi20

    18³ = 5,832 ≥ 5,000. 18 works, so the answer is 18 or smaller: hi = 18.

  5. Step 5 / 6
    lo 1732mid 17 ✗
    lo17mid17hi18

    17³ = 4,913 < 5,000. 17 fails, so does everything below it: lo = 18.

  6. Step 6 / 6
    1732answer 18
    answer18

    The answer is 18: 17³ = 4,913 falls short and 18³ = 5,832 does not.

What it costs

If the answer is a, doubling takes about log₂ a steps to pass it and the search inside the bracket about log₂ a more. So the cost is O(log a), roughly twice a binary search that had been given the right bound, and far better than guessing a huge bound when the answer is small.

TimeO(log a), a = the answer
SpaceO(1)

Where it turns up

  • Sorted data of unknown length. An interface that returns a sentinel past the end, or a file you can seek in but not measure. Double the index until you read the sentinel or a value past the target.
  • Merging and intersecting sorted lists of very different sizes. Walking the long list one step at a time costs its full length. Galloping from the current position to the next useful element costs the logarithm of the distance jumped, which is how adaptive merges in production sort routines handle runs.
  • Answers with no natural ceiling. When the bound you could prove is enormous and the typical answer is small.

In an interview, if you are given a bound like 10¹⁸, a plain search over it costs only about 60 tests. Galloping is worth mentioning, but it is not needed whenever the bound is known.