Binary Search Pattern: Template + 254 LeetCode Problems

What the binary search pattern is

Binary search needs a sorted array far less than it needs a monotone predicate — some property that is false for every candidate below a threshold and true for every candidate above it. Once you can write that predicate, you can bisect anything, including a range of possible answers that is nowhere stored in memory: guess a capacity, ask whether the shipment fits, and move the bound. Most binary search bugs are off-by-one errors in the exit condition, and the cure is to stop searching for a value and search for a boundary instead. Keep the loop as `while lo < hi`, never write `mid - 1` on the side you are keeping, and let the loop end when the two bounds meet — the survivor is the smallest input for which the predicate holds. That single shape covers first occurrence, last occurrence, insertion point and minimum feasible answer, so there is only one template to remember and it terminates by construction.

When to use it

• —The array is sorted, or rotated-sorted, and you want a position rather than a scan.
• —The answer is a number in a known range and checking a candidate is cheaper than finding it.
• —The phrase "minimum largest", "maximum smallest", or "minimise the maximum" appears in the statement.
• —A brute force over the answer range would work but is one order too slow.

The binary search template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 254 problems listed below.

def smallest_feasible(low, high, feasible):
    """Smallest x in [low, high] with feasible(x) true, assuming it is monotone."""
    while low < high:
        mid = low + (high - low) // 2      # floor: biases toward low, never overflows
        if feasible(mid):
            high = mid                     # mid works, so the answer is mid or lower
        else:
            low = mid + 1                  # mid fails, so the answer is strictly higher
    return low

Complexity characteristics

Time

O(log n)

Auxiliary space

O(1)

Every iteration discards half of what is left, so the loop runs log₂ n times. When the search is over a range of possible answers rather than over an array, the cost is O(log W) iterations times whatever the feasibility check costs, where W is the width of the range — that product is the figure to quote, because the check is usually a linear scan and the real complexity is O(n log W). The iterative form uses constant space.

All 254 binary search LeetCode problems

Every problem in the library the binary search pattern applies to, grouped by LeetCode's own difficulty rating. 213 of the 254 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Binary Search pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.