Coding interview pattern
Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
The idea
How the binary search pattern works
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
When to reach for it
- The input is sorted, or you can search a sorted answer space.
- You can write a monotonic yes/no feasibility check over the range.
- The problem asks for a minimum or maximum value that satisfies a constraint.
- An O(n) or O(n log n) scan is too slow and the structure allows O(log n).
Cost
Time & space complexity
| 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
Walkthrough: Minimum eating speed (Koko eating bananas)
- 1Observe that if Koko can finish at speed s, she can finish at any speed greater than s; the predicate is monotonic.
- 2Set the search range from 1 to the largest pile size.
- 3For a candidate speed (the midpoint), compute the hours needed and check it against the deadline.
- 4If she finishes in time, the answer is this speed or smaller, so move the upper bound down; otherwise move the lower bound up.
- 5When the range collapses, the lower bound is the minimum feasible speed.
Translatable skeleton
The shape in pseudocode
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
Curated problem set
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
Common pitfalls
- Off-by-one errors in the boundary update causing infinite loops.
- Mixing half-open and closed interval conventions mid-solution.
- Computing mid as (lo + hi) in languages where that overflows.
- Missing that the answer space, not the array, is what to search.
In the interview
How to communicate it live
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.
Also searched as
binary search on answer - search a sorted array - lower bound upper bound
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- 3.1 Elementary Symbol Tables (binary search) Sedgewick and Wayne, Princeton University
- Competitive Programmer's Handbook: finding the smallest solution (3.3) Antti Laaksonen, CSES
- bisect: Array bisection algorithm Python Software Foundation
Keep going
Related patterns
These techniques share moves with this one, so the practice carries over.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
- Breadth-First Search (BFS)
Explore level by level with a queue; the natural fit for shortest paths on unweighted graphs.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.