Patterns / Binary Search

Binary Search Pattern

Halve the search space each step. Beyond sorted arrays, you can binary-search the answer itself.

What it is

Binary search repeatedly discards half of the remaining possibilities by testing the middle. The classic form finds a value in a sorted array in O(log n). The more powerful form — "binary search on the answer" — applies whenever feasibility is monotonic: if some value v works, every value past it also works (or fails). You then search the range of possible answers, checking feasibility at the midpoint.

When to use it — the signals

• Sorted input and "find / does X exist".
• "Minimum (or maximum) value that satisfies a condition" where the condition is monotonic.
• Answer lies in a numeric range and a feasibility check is cheaper than enumeration.

How it works

A representative implementation in Java:

// Lower bound: first index where nums[i] >= target.
int lo = 0, hi = nums.length;        // half-open [lo, hi)
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;    // avoids overflow
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
}
return lo;

Complexity

O(log n) for a plain search; O(n log n) when each feasibility check costs O(n).

Common pitfalls

• Computing mid as (lo + hi) / 2 and overflowing on large indices.
• Inconsistent interval conventions causing infinite loops or off-by-one.
• Using it when the feasibility predicate is not actually monotonic.

Practice problems

Classic problems where this pattern is the intended approach: Binary Search, Search in Rotated Sorted Array, Koko Eating Bananas, Find Minimum in Rotated Sorted Array. Work through them on the Leet Study home page.