Pattern9 min read

Binary Search (and its many faces)

Binary search isn't just 'find a key' — it's 'monotonic predicate' search, which solves a surprising number of problems in O(log n).

binary-searcharrays

Intro

Binary search is general-purpose. As long as you can phrase your problem as 'is x feasible?' and that predicate is monotone in x, you can binary-search the answer. This is how 'minimum capacity to ship in D days' becomes O(n log range) instead of O(n²).

Key insight

Binary-search the answer space, not the input. The check function does the real work.

Approach

1Decide on the answer range [lo, hi]. Often lo = max element, hi = sum of all.
2Define a boolean feasible(x). It must be monotone: if feasible(x), then feasible(x+1).
3Binary search for the smallest x with feasible(x) == true.
4Watch the invariants: end the loop with lo == hi, return lo.

Complexity

Time

O(n · log range)

Space

O(1)

Where `range = hi - lo` and the check itself is O(n).

Code

LC 1011 — capacity to ship within D daysjava

int shipWithinDays(int[] weights, int D) {
    int lo = 0, hi = 0;
    for (int w : weights) { lo = Math.max(lo, w); hi += w; }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, D, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
boolean canShip(int[] w, int D, int cap) {
    int days = 1, load = 0;
    for (int x : w) {
        if (load + x > cap) { days++; load = 0; }
        load += x;
    }
    return days <= D;
}

Pitfalls

`(lo + hi) / 2` overflows in C++/Java for large values — use `lo + (hi - lo) / 2`.
Wrong invariant: lo = mid + 1 vs hi = mid - 1 changes which side is feasible.
Trying to binary search a non-monotone predicate.

Variants & follow-ups

Find Peak Element (LC 162)
Search in Rotated Sorted Array (LC 33)
Median of Two Sorted Arrays (LC 4)