Modified Binary Search
Binary search on a non-trivial space: rotated arrays, infinite arrays, the answer itself.
Search in rotated sorted array, find first/last position, search in 2D matrix, binary search on answer.
Each iteration discards half of the remaining search space, whether you are searching an array, a rotated array, or 'the answer' itself. Only a few index variables are tracked.
Standard binary search needs a sorted array and an equality target. Modified binary search relaxes both: search a 'sorted-ish' structure (rotated array, mountain array, bitonic) or search the answer itself (smallest capacity, largest minimum). The invariant changes from 'target equals mid' to 'is the answer to the left or right of mid?', and the algorithm becomes 'shrink the range while preserving the property that the answer is in [lo, hi]'.
For rotated arrays, the trick is that at least one half (lo..mid or mid..hi) is always sorted — you check which, then test if target lies in that sorted half to decide which side to recurse. For 'binary search on answer', you need a monotone predicate f(x): if f(x) is true, all values >= x also satisfy it (or vice versa), so you binary-search for the boundary.
Loop termination is the most error-prone part. Use lo < hi when you want to converge on a single index (lo == hi at exit); use lo <= hi when you might find the target exactly at mid and want to return immediately. Update lo = mid + 1 and hi = mid (or hi = mid - 1) based on which one preserves the invariant — mismatched updates cause infinite loops.
Binary search works on any monotone predicate, not just sorted arrays — if you can phrase 'is the answer <= x?' as a check, you can binary-search over x in O(log range) even when the data itself isn't sorted.
- Integer overflow in mid = (lo + hi) / 2 for large lo+hi; use lo + (hi - lo) / 2.
- Choosing the wrong loop condition (< vs <=) for the chosen update rule, causing infinite loops or off-by-one final answers.
- On rotated arrays, comparing nums[mid] to nums[hi] (or nums[lo]) inconsistently — pick one and stick with it.
- For first/last occurrence, returning at first match instead of continuing the search on the appropriate side.
- Confusing 'find target' with 'find insertion point' — they have different return values for the not-found case.
- Rotated sorted array search: one half always sorted, test target's membership.
- First/last occurrence: continue search on the relevant side after a match.
- Search insert position / lower-bound / upper-bound.
- Binary search on answer: capacity to ship in D days, split array largest sum, kth smallest in sorted matrix.
- Peak/mountain search: compare mid to mid+1 to pick the ascending side.
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (/* condition met at mid */) {
return mid; // or record and narrow
} else if (/* target lies left */) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return -1; // or lo, depending on variantProblems using this pattern
3Easiest first · Blind 75 above NeetCode 150