Binary search when there's no sorted array

What is the smallest whole number whose square is at least 2,000?

We could count up from 1 and stop at the first one that works. That'd take 45 steps here, and if we were asked for the smallest x with x² ≥ 10¹⁸, it'd take a billion.

There isn't a sorted list anywhere in that question. What we've got is a test, x * x >= N, that's false for small x and true for all of the x's after some point. It flips over once, and that's all we need for binary search.

What halving buys

If we test at the midpoint, we can throw away half of what's left, whichever way the test goes.

Candidates	Counting up	Halving
1,000	up to 1,000	10
1,000,000	up to 1,000,000	20
10⁹	up to 10⁹	30
10¹⁸	up to 10¹⁸	60

Sixty tests for 10¹⁸. That's why you'll see this come up whenever the answer's a number and checking a guess is cheap, as with ship capacities, minimum speeds, or the largest size of something that'll still fit.

Writing it without off-by-one bugs

Decide what lo and hi mean before you write any of the loop. We'll say that the answer is always somewhere in [lo, hi].

def first_true(lo, hi, test):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if test(mid):
            hi = mid        # mid could be the answer: keep it
        else:
            lo = mid + 1    # mid can't be: drop it
    return lo

first_true(0, 2000, lambda x: x * x >= 2000)   # 45

All of the lines follow from that one decision. If mid passes, it could be the answer, so we set hi = mid and keep it in. If it fails, it can't be, so we set lo = mid + 1. When lo meets hi we've got one value left, and that's our answer.

The rounding matters as well. mid rounds down, so when we're down to two candidates it'll pick the lower of them, and both of the branches will shrink the range. If you rounded up with these two updates, you'd find the loop never ends.

Here's the whole search:

Test	mid	mid²	Result	Still possible
1	1000	1,000,000	passes	0 to 1000
2	500	250,000	passes	0 to 500
3	250	62,500	passes	0 to 250
4	125	15,625	passes	0 to 125
5	62	3,844	passes	0 to 62
6	31	961	fails	32 to 62
7	47	2,209	passes	32 to 47
8	39	1,521	fails	40 to 47
9	43	1,849	fails	44 to 47
10	45	2,025	passes	44 to 45
11	44	1,936	fails	45

So that's eleven tests, where counting up took 45.

There's one thing you should check before you start, and that's that the test switches over exactly once. If it can go true, then false, then true again, there isn't a single boundary for us to find, and binary search will hand you one of several points without any warning that it's done so.

You can step through the search on the original: https://geodesicpartners.co.uk/coding-binary-search-why