Binary search is taught as a lookup: sorted array, find a value, halve the range. That version is worth knowing and comes up rarely. The version that comes up constantly searches over answers rather than over elements, and it does not need a sorted array at all — it needs a monotone predicate.
The precondition
There must be some property P(x) over candidate answers that is false, false, false, then true, true, true — one flip, never back. Then binary search finds the flip. Nothing else is required.
Koko eating bananas is the canonical example. Can she finish at speed x? At speed 1, probably not. Higher speeds are never worse. So 'can finish at speed x' is monotone, and the answer is the smallest x where it becomes true.
The template that has no off-by-one
Use lo < hi with hi = mid and lo = mid + 1, and return lo. The loop invariant is that the answer is always inside [lo, hi], and the range shrinks every iteration because mid is strictly below hi. When lo equals hi the range holds one element, which is the answer.
The lo <= hi form with a separate best variable also works, but it has four places to get a boundary wrong instead of one. Pick one template, use it everywhere, and stop re-deriving the boundaries under time pressure.
Recognising the shape
The phrasing gives it away. 'Minimum capacity such that…', 'maximum value such that…', 'smallest number of days to…'. If the problem asks for an extremal value subject to a feasibility condition, and testing a single candidate is cheap, this is the pattern.
- →Capacity to ship packages within D days.
- →Split an array into k subarrays minimising the largest sum.
- →Smallest divisor giving a threshold-bounded sum.
- →Maximum minimum distance when placing k items.
- →Median of two sorted arrays — binary search the partition point.
Cost analysis
The bound is O(log(range) × cost of one feasibility check). That log factor is over the numeric range, not the array length, so it is usually 30 to 60 iterations even for enormous ranges. The check dominates: if it is linear, the whole solution is O(n log range), which is essentially free.
The failure mode
The predicate is not actually monotone, and the search converges confidently to a wrong answer. Before writing the loop, argue explicitly why a larger candidate can never be worse. If you cannot, the structure is not there — and the fastest way to check is to brute-force small inputs and print the predicate for every candidate. A monotone predicate shows one flip; anything else shows you the problem.
Reading about a pattern is not the same as producing it under time pressure. The problems that drill this are in the curriculum, in order.