4.11.0 — Binary Search: The Pattern

Recognition cue. The input is sorted, or the problem says O(\log n), or — the one people miss — it asks you to minimise the maximum, maximise the minimum, or find the smallest value such that something holds.

The move. Every step discards half the remaining possibilities.

The generalisation that matters. Binary search does not need an array. It needs a monotonic predicate: a yes/no question whose answer, once it flips from false to true, stays true. If you can phrase the problem that way, you can binary search it.

The two shapes

Almost every binary search is one of these. Deciding which one you are writing, before you write it, prevents nearly all boundary bugs.

# SHAPE A — find an exact element. "Bucket model": high is a real index.
low, high = 0, len(a) - 1
while low <= high:                     # a one-element range must still be checked
    mid = low + (high - low) // 2
    if a[mid] == target: return mid
    if a[mid] < target: low = mid + 1
    else: high = mid - 1
return -1

# SHAPE B — find a boundary. "Fence model": high is ONE PAST the end.
low, high = 0, len(a)                  # n items have n+1 possible cut positions
while low < high:                      # stop when the range collapses
    mid = low + (high - low) // 2
    if works(mid): high = mid          # mid might be the answer — keep it
    else: low = mid + 1                # mid is not — discard it
return low                             # low == high == the boundary

Shape B never returns −1 and never tests for equality. It converges on a position. It is the shape for every "smallest value that works" problem, which is most of the hard ones.

The three rules that prevent every common bug

Compute mid as low + (high - low) // 2. Mathematically identical to (low + high) // 2, but it cannot overflow. This was a real bug in Java's standard library, unnoticed for nine years.

Never write low = mid. Integer division floors, so on a two-element range mid == low. Assigning low = mid leaves the range unchanged and the loop runs forever. Either advance past mid, or use shape B where the high = mid branch is the one that keeps it.

Match high to the loop condition. high = len - 1 goes with while low <= high. high = len goes with while low < high. Mixing them is the other half of all binary search bugs.

Binary search on the answer

When there is no array to search, search the space of possible answers. Three conditions:

1. The answer is a number in a known range.
2. "Does value X work?" is cheap to check.
3. If X works, everything above it works too — or everything below, depending on direction.

The cost is O(\text{check} \times \log(\text{range})), and the log is over values, not array length. That is what makes it cheap even when the range is huge.

The seven problems

#	Problem	The one insight
4.11.1	Binary Search	The two shapes, and why mid is computed that way
4.11.2	Search a 2D Matrix	Rows chain, so the grid is one sorted array
4.11.3	Koko Eating Bananas	Search the speed, not the array
4.11.4	Find Minimum in Rotated Array ★	Compare with nums[high], not nums[low]
4.11.5	Search in Rotated Array ★	One half is always cleanly sorted
4.11.6	Time Based Key-Value Store	A floor search — largest key not exceeding the target
4.11.7	Median of Two Sorted Arrays	Search for a cut, not a value

★ marks the Blind 75 subset.

The traps on this pattern

Missing the equality branch. In shape A, forgetting if a[mid] == target makes the search overshoot and return −1 on values that are present.

Seeding a tracker with index 0. In a floor search, initialise the answer to a sentinel that cannot be real data, not to the first element. "No valid entry" is a normal outcome.

Assuming the array is sorted when it is rotated. a[mid] < target no longer tells you the direction. Work out which half is clean first.

Duplicates. They break the rotated-array searches, because equal values at mid and the end carry no information. The fallback is to shrink by one, and the worst case becomes O(n). That degradation is unavoidable.

Floating point in ceiling division. math.ceil(p / k) converts to a float and loses precision at large magnitudes. Use (p + k - 1) // k.

What the interviewer will push on

"Why low + (high - low) // 2?" Overflow safety, and the Java story.

"Where does the infinite loop come from?" Floor division makes mid == low on a two-element range, so low = mid never advances.

"You have no sorted array — how can you binary search?" State the three conditions for binary search on the answer, then give the monotonic property in one sentence.

"Why do you search the shorter array in the median problem?" So the forced index into the other array cannot fall out of bounds.

"What happens with duplicates in a rotated array?" Linear worst case, and it cannot be avoided.

One thing to volunteer: say which shape you are writing before you write it. "This is a boundary search, so high starts one past the end and I never test for equality."

Recall

• Binary search needs a monotonic predicate, not an array. "Once true, always true" is the requirement.
• Shape A (bucket): high = n − 1, while low <= high, tests equality, returns −1 if absent.
• Shape B (fence): high = n, while low < high, no equality test, converges on a position. This is the shape for "smallest value that works".
• mid = low + (high − low) // 2 to avoid overflow. Never low = mid — floor division makes it an infinite loop.
• Binary search on the answer when the problem says minimise the maximum, maximise the minimum, or smallest X such that. The log is over values, not array length.
• Rotated array: compare nums[mid] with nums[high] to find the minimum; find the clean half to search for a target.
• Duplicates destroy the log bound in rotated arrays; the fallback is to shrink by one, giving O(n).
• A floor search returns the largest key at or below the target — remember the best candidate as you go, seeded with a sentinel.

Next: 4.11.1 Binary Search — the base case, written carefully enough that the six problems after it are assembly work.