Skip to content
Work Free practice Coding course Blog Method Results Why me About Enquire Book a call

Coding · Binary search

Understanding the problem

Lesson · 7 min read · Binary search

A search with no array

What is the smallest whole number whose square is at least 2,000? You could count up from 1, squaring as you go, and stop at the first success. That takes 45 steps here, and for "smallest x with x² ≥ 10¹⁸" it takes a billion.

Nothing in that question is a sorted list. What it has instead is a test, x² ≥ N, that is false for small x and true for every x after some point. A test with that shape, false then true with one switch, is all binary search needs.

Halving, counted

Each test at the middle of the remaining range throws away half of it, so a range of size n shrinks to one candidate after about log₂ n tests.

CandidatesTests by countingTests by halving
1,000up to 1,00010
1,000,000up to 1,000,00020
1,000,000,000up to 1,000,000,00030
10¹⁸up to 10¹⁸60

Sixty tests for a range of 10¹⁸ is why this pattern shows up whenever an answer is a number and checking a guess is cheap: ship capacities, minimum speeds, the largest feasible size of anything.

The smallest x with x² ≥ 2000. The bar is the range of candidates still alive; each step keeps the half that can still hold the answer.

  1. Step 1 / 13
    answer range
    0mid 10002000
    lo0hi2000

    Every candidate from 0 to 2000 is still possible. The test "x² ≥ 2000" is false up to some point and true after it; we want the first true.

  2. Step 2 / 13
    answer range
    0mid 10002000
    mid1000mid²1000000

    1000² = 1000000 ≥ 2000. 1000 works, so the answer is 1000 or smaller: hi = 1000.

  3. Step 3 / 13
    answer range
    0mid 5001000
    mid500mid²250000

    500² = 250000 ≥ 2000. 500 works, so the answer is 500 or smaller: hi = 500.

  4. Step 4 / 13
    answer range
    0mid 250500
    mid250mid²62500

    250² = 62500 ≥ 2000. 250 works, so the answer is 250 or smaller: hi = 250.

  5. Step 5 / 13
    answer range
    0mid 125250
    mid125mid²15625

    125² = 15625 ≥ 2000. 125 works, so the answer is 125 or smaller: hi = 125.

  6. Step 6 / 13
    answer range
    0mid 62125
    mid62mid²3844

    62² = 3844 ≥ 2000. 62 works, so the answer is 62 or smaller: hi = 62.

  7. Step 7 / 13
    answer range
    0mid 3162
    mid31mid²961

    31² = 961 < 2000. 31 is too small, and so is everything below it: lo = 32.

  8. Step 8 / 13
    answer range
    32mid 4762
    mid47mid²2209

    47² = 2209 ≥ 2000. 47 works, so the answer is 47 or smaller: hi = 47.

  9. Step 9 / 13
    answer range
    32mid 3947
    mid39mid²1521

    39² = 1521 < 2000. 39 is too small, and so is everything below it: lo = 40.

  10. Step 10 / 13
    answer range
    40mid 4347
    mid43mid²1849

    43² = 1849 < 2000. 43 is too small, and so is everything below it: lo = 44.

  11. Step 11 / 13
    answer range
    44mid 4547
    mid45mid²2025

    45² = 2025 ≥ 2000. 45 works, so the answer is 45 or smaller: hi = 45.

  12. Step 12 / 13
    answer range
    44mid 4445
    mid44mid²1936

    44² = 1936 < 2000. 44 is too small, and so is everything below it: lo = 45.

  13. Step 13 / 13
    answer range
    45mid 4546
    answer45

    lo and hi meet at 45: 44² = 1936 is too small and 45² = 2025 is enough. 11 tests instead of the 45 it takes to count up from 1.

The invariant that prevents off-by-one errors

Most binary search bugs come from not deciding what lo and hi mean. Decide it once and every line follows from it. Here the invariant is: the answer is always in [lo, hi].

  • If mid passes the test, it might be the answer, so it must stay in the range: hi = mid, not mid − 1.
  • If mid fails, it cannot be the answer: lo = mid + 1.
  • The loop runs while lo < hi; when they meet, the range holds exactly one value, and the invariant says it is the answer.
  • mid = lo + (hi − lo) / 2 rounds down, so with two candidates left it picks the lower one, and either branch shrinks the range. Rounding up here, with this pair of updates, loops for ever.

Binary search needs a test that switches once. If the test can switch back (true, false, true) there is no single boundary to find, and the method will silently return one of several points.