Coding interview pattern
Halve the search space each step over any monotonic condition, not just sorted arrays.
The idea
Binary search is the most under-applied pattern in interviews because candidates only recognise it on a literally sorted array. The real abstraction is broader: whenever you can phrase a question as a monotonic predicate (a boolean that is false, false, ..., false, true, true, ..., true across the search range), you can binary-search for the boundary in logarithmic time. The array does not have to hold your answer; the answer space itself can be searched.
The classic form locates a target in a sorted array by repeatedly comparing the middle element and discarding half. The more powerful form is binary search on the answer: for problems like the minimum capacity to ship packages in d days, or the smallest divisor under a threshold, you binary-search over the possible answers and use a feasibility check as the predicate. If a candidate answer works, everything larger works too, which gives the monotonicity binary search needs.
Correctness lives in the loop invariant and the boundary update. Decide up front whether you want the first true or the last false, keep the half-open or closed interval consistent, and make sure the loop always shrinks the range so it terminates. Most binary-search bugs are off-by-one errors at the boundary, not logic errors in the middle.
Recognition
Cost
| Operation | Time | Space |
|---|---|---|
| Search a sorted array | O(log n) | O(1) |
| Binary search on answer | O(log(range) * cost-of-check) | O(1) |
| Lower/upper bound | O(log n) | O(1) |
Worked example
Translatable skeleton
Language-agnostic on purpose. Translate it to your language of choice.
lo, hi = min_ans, max_ans; while lo < hi: mid = (lo + hi) // 2; if feasible(mid): hi = mid; else: lo = mid + 1; return loPractice
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Binary Search | Easy | The textbook sorted-array search. |
| Search Insert Position | Easy | Lower-bound boundary search. |
| Find Minimum in Rotated Sorted Array | Medium | Binary search with a rotation invariant. |
| Koko Eating Bananas | Medium | Binary search on the answer. |
| Capacity to Ship Packages Within D Days | Medium | Feasibility-check binary search. |
| Median of Two Sorted Arrays | Hard | Partition-based binary search, the hardest classic. |
Avoid these
In the interview
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
State your loop convention up front, whether the interval is half-open or closed and whether you are hunting the first true or last false, then keep it consistent; most binary-search bugs are convention drift mid-solution.
For binary-search-on-answer problems, the breakthrough sentence is if speed s works then any larger speed works, so the predicate is monotonic; say that explicitly to show you saw the hidden structure.
Always argue that the range strictly shrinks each iteration, which is your proof that the loop terminates rather than spins forever on an off-by-one boundary.
binary search on answer - search a sorted array - lower bound upper bound
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Keep going
Track a contiguous subarray or substring without re-scanning it from scratch.
Walk two indices toward or alongside each other to avoid a nested loop.
Solve overlapping subproblems once, store the results, and build the answer up.
Explore level by level with a queue; the natural fit for shortest paths on unweighted graphs.
See all coding patterns, the coding questions for your role, and the behavioral round.