Finding where a property flips

Binary Search

Finding where a property flips

The general form of binary search, which happens to make exact-match search a one-line special case.

Key idea

What binary search actually needs

Binary search is usually introduced as looking up a value in a sorted array. That framing is too narrow, and it is why the harder problems in this unit feel like different techniques when they are not.

The real requirement is weaker. You need a range of candidates and a yes-or-no property that is false for a while and then true for the rest. One flip, never flipping back. Given that, you can find the flip point in O(log n) by asking about the middle and throwing away the half that cannot contain it.

Sortedness matters only because it happens to make properties like value >= target behave that way.

Why it works

The property has to be monotone

Write out the property as a row of falses followed by a row of trues. If your property produces false true false, binary search cannot find anything, because testing the middle tells you nothing about which side the answer is on.

So the first question for any candidate binary search is not is this sorted. It is: is my property monotone over this range? Answer that before writing a loop.

The template

One loop shape covers every boundary question. It narrows a half-open range and finishes with low sitting on the first true.

Why it works

Why each branch does what it does

The invariant is that the answer always lies in the half-open range from low to high. Every line preserves it.

When the property holds at mid, mid itself could be the earliest true, so it must stay in the range and high becomes mid rather than mid - 1. When it does not hold, mid is definitely not the answer and can be discarded, so low becomes mid + 1.

That asymmetry is not arbitrary. It follows from the range being half-open, and it is why this version never loops forever: low strictly increases or high strictly decreases every pass.

Gotcha

The infinite loop this shape avoids

Writing high = mid together with a low <= high condition, or computing mid by rounding up, produces loops that get stuck when two candidates remain. The range stops shrinking and the loop spins.

Rather than memorizing which combinations are safe, check one thing before you run: does every branch make the range strictly smaller? If a branch can leave low and high unchanged, you have found your bug.

Tip

About `low + (high - low) // 2`

In languages with fixed-width integers, (low + high) // 2 can overflow when both are large, and the subtraction form avoids it. Python integers grow as needed, so overflow genuinely cannot happen here and both forms are correct.

The subtraction form is still worth writing. Interviewers ask about it, and the habit transfers to languages where it is not optional.

Key idea

Exact match is a special case

Once you can find the first position where value >= target, exact match is one comparison away: look at that position and check whether it actually holds the target.

This is worth internalizing because the boundary version answers questions the exact version cannot, such as where would this go, how many are below it, and what is the closest one. Learning only the exact-match loop leaves you rewriting it from scratch every time the question shifts slightly.

Predict the output: which half survives

This searches for the first index whose value is at least 5, and prints the range at each step before returning. Type every line it prints.

Boundary drills

Write the boundary loop three times with different properties. first_at_least returns the first index whose value is at least the target, or the list length. count_below returns how many values are strictly below the target. find_exact returns the index of the target or -1, built on first_at_least.

Python
Loading editor…

Tests

values = [1, 3, 3, 5, 8]
print(first_at_least(values, 3), first_at_least(values, 4), first_at_least(values, 9))
print(count_below(values, 3), count_below(values, 0), count_below(values, 100))
print(find_exact(values, 5), find_exact(values, 4), find_exact([], 1))

Output

Run the tests when you are ready.
← Previous