Coding Interview: Patterns & DSA · Sorting, Searching & Heaps · Lesson 1 of 3
Binary search patterns
Binary search finds a target in a sorted array in O(log n) by repeatedly halving the search space. Its deeper power is binary search on the answer: whenever a yes/no condition is monotonic (false, false, ..., true, true) over a range, you can binary-search for the boundary.
def binary_search(a, target): lo, hi = 0, len(a) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 # avoids overflow if a[mid] == target: return mid if a[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
- Find boundaries: leftmost/rightmost occurrence, first element >= target (lower/upper bound).
- Rotated sorted array: one half is always sorted — decide which, then search it.
- Binary search the answer: 'minimum capacity to ship in D days', 'smallest divisor', 'Koko eating bananas' — guess a value, test feasibility in
O(n), narrow the range.
Off-by-one and overflowThe two classic bugs: infinite loops from wrong
lo/hi updates, and computing mid as (lo + hi) / 2 — which can overflow in fixed-width languages (Java, C++, Go). Python ints can't overflow, but write lo + (hi - lo) // 2 anyway; it's the portable habit interviewers expect. And be deliberate about whether the boundary is inclusive.Recognize itThe tell for binary search: the data is sorted, or the problem asks for a minimum/maximum value satisfying a monotonic condition, and a linear scan would be too slow.
O(log n) or O(n log(range)) is the target.◆ Lock it in
- Binary search is
O(log n)on sorted data; halve the space each step. - Binary search on the answer works whenever feasibility is monotonic.
- Use
lo + (hi - lo) // 2and be careful with inclusive/exclusive bounds.
Feynman drill — say it out loudExplain 'binary search on the answer' and give one example where the array is not what you search.
Step 1 rate your confidence · Step 2 pick your answer
Binary search on the answer (not on an array) is valid whenever:
Step 1 — how sure are you?