← All patterns

Modified Binary Search

Binary search beyond plain sorted arrays: rotated, bitonic, peaked, on the answer value, or on a real-valued range. The only requirement is a monotone predicate.

20 problems 5 Easy 8 Medium 7 Hard

Binary search generalizes far beyond 'find element in sorted array'. The key invariant is a monotone predicate: if you can answer 'is the answer at most x?' in O(f(n)) and the predicate is monotone in x, you can binary-search the answer space in O(f(n) log range). Works on rotated arrays (one half is always sorted), peaked arrays (follow the slope), real-valued ranges (fixed iteration count or epsilon), and combinatorial choices (capacity, rate, time).

Mastering both 'find equal' and 'find boundary' templates is the prerequisite to all variants.

When to reach for this pattern

  • 'Find the smallest / largest value such that P(x) holds'
  • Rotated, bitonic, or otherwise structured-but-not-globally-sorted arrays
  • Real-valued answer (use fixed iteration count or epsilon)
  • 'Capacity' / 'rate' / 'time' problems where the predicate is monotone

Canonical template 

// find first index satisfying monotone predicate P
int lo = LO, hi = HI;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (P(mid)) hi = mid;
    else lo = mid + 1;
}
return lo;

// rotated-array search: one half is always sorted
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    if (nums[lo] <= nums[mid]) {
        if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
        else lo = mid + 1;
    } else {
        if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
        else hi = mid - 1;
    }
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • (lo + hi) / 2 can overflow — use lo + (hi - lo) / 2
  • Wrong template: lo <= hi with mid - 1/mid + 1 (find-equal) vs lo < hi with mid/mid + 1 (find-boundary)
  • Predicate must be monotone — verify before reaching for binary search
  • Off-by-one in 'upper-bound' style — adjust mid = lo + (hi - lo + 1) / 2

Related patterns

Top K Elements Sort and Search

Problems (20)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.