Sweaty Imposter

Modified Binary Search Pattern

CodingMid2 min read · 8 problemsUpdated

Binary search on a non-trivial space: rotated arrays, infinite arrays, the answer itself.

When to Use It

Search in rotated sorted array, find first/last position, search in 2D matrix, binary search on answer.

Classic example: Search in a rotated sorted array.

How It Works

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.

Key Insight

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.

4567012lomidhi
Rotated array: at each step decide which half is sorted, then narrow.

Worked Example

Search in a rotated sorted array

nums = [4, 5, 6, 7, 0, 1, 2], target = 0

  1. lo=0, hi=6, mid=3: the left half [4, 5, 6, 7] is sorted and 0 isn't in its range, so lo = 4
  2. lo=4, hi=6, mid=5: the left half [0, 1] is sorted and 0 is in its range, so hi = 4
  3. lo=4, hi=4, mid=4: nums[4] = 0, found

Result: Index 4 in three probes. At least one half is always sorted, and checking whether the target falls inside that half's range decides which side to keep.

Templates

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 variant

Common Pitfalls

  • 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.

When It Breaks

  • You need a predicate that flips exactly once across the search space (false, false, true, true). The array itself doesn't have to be sorted, but if the predicate flips back and forth, halving throws answers away.
  • Duplicates in a rotated array (e.g. [1, 1, 1, 0, 1]) can make nums[lo], nums[mid], and nums[hi] all equal, so neither half is provably sorted. You can only shrink by one, and the worst case becomes O(n).
  • Binary search needs O(1) access by index. On a linked list each probe costs O(n), so a linear scan is just as fast.

Variations

  • 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.

Big O

Time
O(log n)
Space
O(1)
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.
Next PatternBitwise XOR