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.
Almost every binary search is one of these. Deciding which one you are writing, before you write it, prevents nearly all boundary bugs.
python
# SHAPE A — find an exact element. "Bucket model": high is a real index.low, high = 0, len(a) - 1 # (1)while low <= high: # (2) a one-element range must still be checked mid = low + (high - low) # (3) 2 if a[mid] == target: return mid # (4) if a[mid] < target: low = mid + 1 # (5) else: high = mid - 1return -1 # (6)# SHAPE B — find a boundary. "Fence model": high is ONE PAST the end.low, high = 0, len(a) # (7) n items have n+1 possible cut positionswhile low < high: # (8) stop when the range collapses mid = low + (high - low) // 2 if works(mid): high = mid # (9) mid might be the answer — keep it else: low = mid + 1 # (10) mid is not — discard itreturn low # (11) low == high == the boundary
The template, line by line.
(1) Shape A searches inside the list, so high is the last real position. (2) A range of one number still has to be checked, so loop while low <= high. (3) The middle, written so it cannot overflow in fixed-size languages. (4) Found the target. (5) The middle is too small, so the target can only be to its right; skip past mid. Otherwise it can only be to the left. (6) The range emptied without finding it.
(7) Shape B looks for the first position where a yes/no question turns to "yes". A list of n items has n + 1 such cut positions, so high starts one past the end. (8) Stop when the range shrinks to one position. (9) If mid works, it might be the answer, so keep it with high = mid. (10) If it does not work, nothing at or before it can be the answer, so move past it. (11)low and high meet on the first position that works.
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.
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.
When there is no array to search, search the space of possible answers. Three conditions:
The answer is a number in a known range.
"Does value X work?" is cheap to check.
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.
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.
"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.