Halve the search space every step - on sorted arrays, but also on answer ranges you can test monotonically.
What the binary search pattern is
Binary search maintains a range that provably contains the answer and halves it every step by testing the middle: O(log n) instead of O(n). The textbook version finds an exact value in a sorted array, but interviews rarely stop there. The general form needs only a monotonic predicate - a yes/no test that flips exactly once as you sweep across the search space. Everything before some boundary answers 'no', everything after answers 'yes', and binary search finds that boundary.
That generalization unlocks the pattern's real power: searching the answer space. In 'minimum eating speed to finish bananas in h hours', nothing in the input is sorted - but the predicate 'can finish at speed k?' is monotonic in k (if speed k works, every faster speed works too). Binary search over k finds the minimum workable speed without the input being sorted at all.
How to recognize it
Direct signals: sorted (or rotated-sorted) input, or an explicit O(log n) requirement. Subtler signals: the question asks to minimize a maximum or maximize a minimum ('smallest capacity that ships all packages in d days', 'largest minimum distance between cows') - these are almost always binary search on the answer with a greedy feasibility check inside.
The litmus test: can you define a predicate over an ordered domain that is false…false, then true…true? If checking the predicate for one candidate is cheap (say O(n)), binary search finds the boundary in O(n log range). If the predicate can flip back and forth, binary search is unsound - that is its one hard requirement.
The boundary template (learn one, derive the rest)
Most binary search bugs come from mixing incompatible conventions for mid, the bounds update, and the loop condition. The fix is to memorize a single boundary-finding template and derive everything from it: find the first index where a predicate is true. Half-open bounds [lo, hi), shrink until lo == hi, and never let mid escape the current range.
With this one template: exact search = first index where a[i] ≥ target, then check equality. Lower bound = first i with a[i] ≥ target. Upper bound = first i with a[i] > target. Minimize-the-answer problems = first candidate where 'feasible(candidate)' is true. No ±1 case analysis, no infinite loops.
pseudocode
# returns the first index in [lo, hi) where check(i) is true,
# or hi if it is never true
lo = 0, hi = n
while lo < hi:
mid = lo + (hi - lo) / 2 # floor; avoids overflow
if check(mid): hi = mid # mid might be the boundary - keep it
else: lo = mid + 1 # mid is before the boundary - discard it
return lo
Complexity
O(log n) probes for a direct array search. For answer-space searches, O(f(n) · log(range)) where f(n) is the feasibility check - e.g., shipping capacity: O(n log(sum − max)). Space is O(1) iterative. The log factor is why binary search survives enormous ranges: an answer space of a billion candidates takes about 30 probes.
Common pitfalls
The classic infinite loop: with inclusive bounds and lo = mid (instead of mid + 1), a two-element range can make mid == lo forever. The half-open template above cannot loop: the range strictly shrinks every iteration.
mid = (lo + hi) / 2 overflows in fixed-width integer languages when lo + hi exceeds the type's max; write lo + (hi − lo) / 2.
Off-by-one at the edges: forgetting that the boundary may not exist (return value hi means 'never true') and dereferencing a[lo] without checking.
Using binary search on a non-monotonic predicate. If 'works(k)' can be true, then false, then true again, the halving argument is invalid - no amount of template discipline fixes a broken precondition.
In rotated-array problems, forgetting that one half is always sorted - that fact, not the mid value alone, is what tells you which half to keep.
Worked examples
1. First and last position of a target in a sorted arraymedium
Given a sorted array with duplicates and a target, return the first and last indexes of the target, or (−1, −1) if absent.
Two boundary searches, not one exact search: the first occurrence is the first index where a[i] ≥ target; one past the last occurrence is the first index where a[i] > target.
Run the boundary template twice with those two predicates. Both are monotonic over a sorted array - false for a prefix, true for the rest.
First occurrence: if the returned index is in range and a[lo] equals the target, it is the answer; otherwise the target is absent. Last occurrence: the second search's result minus one.
Two O(log n) passes, O(1) space - and zero special-casing for duplicates, which is the whole point of thinking in boundaries.
pseudocode
first = firstIndexWhere(i => a[i] >= target) # boundary template
if first == n or a[first] != target: return (-1, -1)
afterLast = firstIndexWhere(i => a[i] > target)
return (first, afterLast - 1)
Remember: Duplicates stop being a special case the moment you search for boundaries instead of exact matches.
2. Search in a rotated sorted arraymedium
A sorted array was rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2]). Find a target's index in O(log n).
The array as a whole is not sorted, so plain binary search cannot run - but any split of a rotated array leaves at least one half properly sorted. Compare a[lo] with a[mid] to learn which half that is.
The sorted half admits a definitive range check: if the target lies within its endpoints, recurse into it; otherwise the target must be in the other half - messy, but the only place left.
Either way, half the range is discarded per step, preserving O(log n).
The lesson generalizes: binary search does not need global order, only a way to certify which half can be safely discarded at each step.
pseudocode
lo = 0, hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2
if a[mid] == target: return mid
if a[lo] <= a[mid]: # left half is sorted
if a[lo] <= target < a[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half is sorted
if a[mid] < target <= a[hi]: lo = mid + 1
else: hi = mid - 1
return -1
Remember: Binary search needs a certifiable discard, not a fully sorted array - the sorted half provides the certificate.
3. Koko eating bananas (search the answer space)medium
Given pile sizes and h hours, find the minimum eating speed k (bananas/hour) such that all piles are finished within h hours; each hour Koko eats from one pile.
Nothing here is sorted, and the input is piles - yet the question is 'minimum k such that…', which is a boundary question over the ordered domain of speeds.
Define feasible(k) = sum over piles of ceil(pile / k) ≤ h. This is monotonic: eating faster never takes more hours. False for tiny k, true from some threshold onward.
The search range is k ∈ [1, max(piles)] - above max(piles), speed no longer helps. Binary search that range with the boundary template, running the O(n) feasibility check per probe.
O(n log max(piles)) total. This 'binary search + greedy check' pairing solves a whole family: ship capacity, split array largest sum, minimum days for bouquets.
pseudocode
feasible(k) = (sum of ceil(pile / k) for each pile) <= h
lo = 1, hi = max(piles)
while lo < hi:
mid = lo + (hi - lo) / 2
if feasible(mid): hi = mid
else: lo = mid + 1
return lo
Remember: When the question is 'smallest value that works', binary search the answers, not the input - all you need is a monotonic feasibility test.
4. Find the minimum in a rotated sorted arraymedium
A sorted array of distinct values was rotated at an unknown pivot. Return its minimum element in O(log n).
The minimum is the rotation point - the one place where order 'resets'. Frame it as a boundary: mark each index i with the predicate a[i] ≤ a[n−1]. The unsorted prefix answers false; the suffix containing the minimum answers true.
That predicate is monotonic (false…false, true…true), so the boundary template applies directly: find the first index where a[i] ≤ a[n−1].
Compare a[mid] to a[n−1]: if a[mid] > a[n−1], the minimum is strictly right of mid; otherwise mid could be the minimum, so keep it in range.
The answer is a[lo] after the loop. No rotation-point special cases - the predicate framing dissolved them.
pseudocode
lo = 0, hi = n - 1
while lo < hi:
mid = lo + (hi - lo) / 2
if a[mid] > a[n-1]: lo = mid + 1 # min is right of mid
else: hi = mid # mid could be the min
return a[lo]
Remember: Recasting 'find the special position' as 'find where a monotonic predicate first turns true' is the master move of this pattern.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1What is the one property a predicate must have for binary search over it to be correct?
It must be computable in O(1)
✓ It must be monotonic: once it turns true, it stays true across the ordered domain
It must be true for at least one candidate
It must involve a sorted array
Binary search discards half the domain based on one probe. That is only sound if the predicate never flips back - false…false, true…true. Cheap evaluation is nice, existence can be handled, sortedness is just one way to get monotonicity.
2Why is mid computed as lo + (hi − lo) / 2 rather than (lo + hi) / 2?
It rounds toward the upper half, which converges faster
✓ lo + hi can overflow fixed-width integers; the subtraction form cannot
The two are different values in general
It avoids a division by zero
Mathematically they are equal, but in fixed-width arithmetic lo + hi can exceed the integer maximum and wrap negative. A classic real-world bug - it lived in the JDK's binary search for nine years.
3'Minimum ship capacity to deliver all packages within d days' - why is this a binary search problem?
The package weights are sorted
✓ feasible(capacity) is monotonic, so the minimum workable capacity is a boundary that halving can find
The number of days is a power of two
It isn't - it requires dynamic programming
If a capacity works, every larger capacity works: monotonic. Binary search the capacity range with a greedy O(n) simulation as the feasibility check - the standard 'minimize the max' recipe.
4In the half-open boundary template, why does check(mid) being true set hi = mid instead of hi = mid − 1?
To make the loop terminate faster
✓ Because mid itself might be the first true index, and hi = mid − 1 could discard the answer
Because hi must always stay even
It is a stylistic choice with no effect
The invariant is that the answer lies in [lo, hi). A true mid is a candidate boundary, so it must remain inside the range; excluding it risks discarding the only answer. False mids are safely excluded with lo = mid + 1.
5When searching a rotated sorted array, what fact makes each halving step safe?
The middle element is always the largest
✓ At least one of the two halves is always properly sorted, and a sorted half supports a definitive in-range test
The rotation pivot is always in the left half
Rotated arrays contain no duplicates
Splitting a rotated-sorted array leaves at least one half in sorted order. That half's endpoints give a certain answer to 'is the target in here?', which justifies discarding one half every step.
Frequently asked questions
Can I use binary search when the array isn't sorted?
Not on the array directly - but if the question is 'smallest/largest value satisfying a condition' and that condition is monotonic, you can binary search the answer space instead. Sortedness is one source of monotonicity, not a requirement of the pattern.
How do I avoid off-by-one errors in binary search?
Standardize on one template - half-open [lo, hi), loop while lo < hi, hi = mid on true, lo = mid + 1 on false - and derive every variant from it. Bugs come from mixing conventions, not from binary search being inherently tricky.
What is 'binary search on the answer'?
Instead of searching positions in the input, you search candidate answers: guess a value, run a (usually greedy) feasibility check, and use monotonicity to discard half the candidates. It is the standard approach for minimize-the-maximum and maximize-the-minimum problems.
How do I recognize a binary search problem that doesn't mention sorting?
Look for 'minimum X such that…' or 'maximum X such that…' where feasibility only improves as X grows (or shrinks). Ship capacities, eating speeds, split sizes, and distances are classic disguises.