Binary Search Patterns: 7 Variations You Must Know

Binary Search Patterns: 7 Variations Beyond “Find the Element”

Most people learn binary search as “find 7 in a sorted list” and then freeze when an interview asks for the minimum eating speed, the first bad build, or a peak in an unsorted array. These problems are all binary search, but the textbook version never taught you to see them that way.

In this post, you’ll learn one reusable template that covers seven patterns: lower bound, upper bound, rotated arrays, peak finding, search on answer, minimize-the-maximum, and counting-based search over a value range. You’ll get a traced dry run, Python and C++ templates, 12 practice problems, and the mistakes that cause most wrong answers. If you want the cost model behind everything here, start with our complete guide to time and space complexity.

Phase 1: The Problem

Your CI system has 1,000,000 commits between the last release and today. The release is broken, and you need the first commit that broke it. Testing one commit takes a few minutes of build and test time.

The brute-force approach checks commits from oldest to newest until one fails. That’s O(n), about a million builds in the worst case, which is hopeless.

The usual fix is “binary search,” and this is where it goes wrong. Many people think binary search needs a target value and a sorted array. Here you have neither. You have a history where commits behave like good, good, good, ..., bad, bad, bad. You aren’t looking for a value. You’re looking for the place where behavior changes.

The same blind spot shows up in a classic array problem. Given a sorted array with duplicates, count how many times x appears. The naive approach finds any occurrence of x, then walks left and right to count. If the whole array is x, that walk is O(n) and you’ve lost the logarithmic speedup you came for.

Both problems need a different question. Instead of “where is x?”, ask “where does the answer flip from false to true?” That one change of question is the whole post.

Phase 2: The Pattern

The mental model: a row of light switches

Imagine a long hallway of light switches. Every switch left of some point is OFF, and every switch from that point onward is ON. You can flip-test any single switch in one step, and you want the first ON switch.

Binary search does this in O(log n). Test the middle switch. If it’s ON, the boundary is at or left of it, so throw away everything to the right. If it’s OFF, the boundary is strictly right of it, so throw away that switch and everything left of it.

index:  0  1  2  3  4  5  6  7  8  9
pred:   F  F  F  F  F  T  T  T  T  T
                      ^
                 first True (the answer)

The function that tells you ON or OFF is a predicate. The one requirement is that it is monotonic: once it turns True, it stays True. Sorted data is just one common way to get a monotonic predicate. For example, a[i] >= x on a sorted array is monotonic.

This framing is a small shift, but it changes how you code the problem. You stop writing a new loop for every problem and write the predicate instead.

When to recognize the pattern

Look for these phrases in a problem statement:

• “Find the first / last / smallest / largest X such that…”
• “Minimum speed / capacity / time / size so that it’s possible to…”
• “Minimize the maximum” or “maximize the minimum”
• “Given a sorted (or rotated, or mountain-shaped) array…”
• A required complexity of O(log n), or n up to 10⁹ or more, where scanning is impossible
• “Is it feasible with X?” is easy to check, but “what’s the best X?” is hard

What most tutorials get wrong

Most tutorials show three or four different loop shapes (lo <= hi with mid ± 1, lo < hi with hi = mid, and so on) and tell you to memorize them. That’s why people keep writing off-by-one bugs: they’re picking a shape by feel each time.

The sharper approach is to use one loop shape for every problem and move all the problem-specific logic into the predicate. The second thing tutorials skip is that correctness depends on monotonicity, not sortedness. If your predicate isn’t monotonic, the code runs fine and returns garbage. We’ll come back to this in Phase 7.

Binary search is also famously easy to get wrong. Jon Bentley’s Programming Pearls noted that the first binary search appeared in 1946, but a version correct for all array sizes didn’t appear until 1962 (as quoted in Joshua Bloch’s 2006 post). Using a single, well-understood template is how you avoid becoming a data point in that history.

Phase 3: Step-by-Step Walkthrough

Let’s trace the lower bound (first index where a[i] >= x) on this array with x = 3:

a = [1, 3, 3, 3, 5, 8]      indices 0..5, n = 6

The search range is half-open [lo, hi), starting at lo = 0, hi = 6. Here hi = n means “no True exists, so the answer is past the end.”

Three steps for six elements, and we landed on the first 3 even though duplicates exist.

Now the upper bound (first index where a[i] > 3), on the same array:

The count of 3s is 4 - 1 = 3, with no walking and no special case for duplicates. The loop always follows the same flow:

Two design choices keep this loop safe:

• hi = mid on True keeps mid as a candidate, because it might be the first True.
• lo = mid + 1 on False guarantees progress. mid is known not to be the answer, and the range shrinks every iteration, so there are no infinite loops.

Phase 4: Code Templates

Python

from typing import Callable

def first_true(lo: int, hi: int, pred: Callable[[int], bool]) -> int:
    """Smallest i in [lo, hi) with pred(i) True; returns hi if none.
    Requires pred to be monotonic: False...False True...True.
    Time: O(log(hi - lo)) predicate calls. Space: O(1).
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2   # overflow-safe habit; matters in C++/Java
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


# Variation 1: lower bound (first index with a[i] >= x)
def lower_bound(a: list[int], x: int) -> int:
    return first_true(0, len(a), lambda i: a[i] >= x)

# Variation 2: upper bound (first index with a[i] > x), plus count
def upper_bound(a: list[int], x: int) -> int:
    return first_true(0, len(a), lambda i: a[i] > x)

def count_occurrences(a: list[int], x: int) -> int:
    return upper_bound(a, x) - lower_bound(a, x)   # O(log n) total

# Last index with a[i] <= x is upper_bound(a, x) - 1 (check >= 0 before using)

The standard library already does the first two. Python’s bisect_left and bisect_right are exactly lower and upper bound. The docs also note that these functions locate an insertion point rather than test for a specific value. Since Python 3.10, they take a key parameter, so you can bisect over any sequence, including a range:

from bisect import bisect_left

# first k in [1, 10**9] where feasible(k) is True  (Python 3.10+)
# bool ordering is False < True, so searching for True finds the boundary
def first_true_bisect(lo, hi, pred):
    return lo + bisect_left(range(lo, hi), True, key=pred)

Per the docs, key is applied to the array elements and not to the search value, which is why we pass True directly.

What problem it solves: one routine for “first index where something becomes true,” so you never re-derive the loop.

Key parts: half-open range [lo, hi), hi = mid on True, lo = mid + 1 on False, return lo.

Production notes: O(log n) comparisons. In production code, call your language’s library routine rather than writing your own. If your predicate is expensive (a network call, a build), the log factor matters a lot, which is exactly why git bisect exists (Phase 8).

C++

#include <vector>
#include <algorithm>

// Smallest i in [lo, hi) with pred(i) true; returns hi if none.
// Time: O(log(hi - lo)) predicate calls. Space: O(1).
template <class Pred>
long long first_true(long long lo, long long hi, Pred pred) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;  // never (lo + hi) / 2 with 32-bit ints
        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

// Usage: lower bound over a sorted vector<int> a
// long long i = first_true(0, a.size(), [&](long long k){ return a[k] >= x; });

// Library equivalents: std::lower_bound(a.begin(), a.end(), x)
//                      std::upper_bound(a.begin(), a.end(), x)

The C++ standard library has a more general version. std::partition_point takes a predicate and finds where it flips, and the cppreference page notes that lower_bound is a special case of it, with predicate e < value.

The mid line is where history bites. Bloch’s post describes how (low + high) / 2 can overflow for very large arrays, and notes that the bug sat in a widely used JDK implementation until it was reported. The fix is low + (high - low) / 2. Python integers don’t overflow, but build the habit anyway, because your C++ and Java interview code will need it.

Production notes: the template needs only a monotonic predicate, so it works over long long ranges and not just array indexes. That makes the next five patterns possible.

Phase 5: Variations

Variations 1 and 2 are the two boundary searches above. Here are the other five, all built on first_true.

Variation 3: Rotated sorted array

A sorted array was rotated at an unknown pivot, like [6, 7, 9, 1, 2, 4]. The array isn’t sorted, but this predicate is monotonic: “is a[i] at most the last element?” It reads False, False, False, True, True, True. The first True is the pivot (the minimum), assuming distinct values.

def search_rotated(a: list[int], target: int) -> int:
    """Distinct values. Returns index or -1. O(log n)."""
    if not a:
        return -1
    n = len(a)
    p = first_true(0, n, lambda i: a[i] <= a[-1])   # pivot = index of minimum
    # a[p:] and a[:p] are each sorted; pick the half that could hold target
    lo, hi = (p, n) if target <= a[-1] else (0, p)
    i = first_true(lo, hi, lambda i: a[i] >= target)
    return i if i < n and a[i] == target else -1

Two clean binary searches instead of one tangled loop with four cases. The catch is duplicates: with [1, 1, 1, 0, 1] the predicate stops being monotonic, and the worst case degrades to O(n) (this is the “Search in Rotated Sorted Array II” variant).

Variation 4: Peak finding

Find an index where a[i] > a[i+1] first becomes true, in an unsorted array where adjacent elements differ. The predicate a[i] > a[i+1] is not globally monotonic, yet binary search still works. The reason is an invariant: if a[mid] < a[mid+1], the slope is rising, so a peak must exist to the right (the array either keeps climbing to the end, or turns down at some point). If a[mid] > a[mid+1], a peak exists at mid or to its left.

def find_peak(a: list[int]) -> int:
    """Adjacent elements differ. Returns the index of some peak. O(log n)."""
    return first_true(0, len(a) - 1, lambda i: a[i] > a[i + 1])

If no i satisfies the predicate, the function returns n - 1, and the last element is a valid peak because the array is rising into it. The takeaway: you don’t always need sortedness or a perfectly monotonic predicate. You need an invariant that guarantees the answer stays inside [lo, hi].

Variation 5: Search on the answer

You aren’t searching an array at all. The problem says “minimum eating speed so Koko finishes all piles in h hours.” Given a speed k, checking feasibility is easy: total hours is the sum of ceil(pile / k). And feasibility is monotonic, because if speed k works, then k + 1 works.

def min_eating_speed(piles: list[int], h: int) -> int:
    def feasible(k: int) -> bool:
        return sum((p + k - 1) // k for p in piles) <= h
    return first_true(1, max(piles) + 1, feasible)

The search space is the range of possible answers, 1 up to max(piles). Total cost is O(n log M), where M is the largest pile. You turned an optimization problem into a series of yes/no questions.

Variation 6: Minimize the maximum

Ship packages in order within D days, minimizing the ship’s capacity. The feasibility check is a greedy simulation: load packages until the next one would exceed capacity, then start a new day.

def ship_within_days(weights: list[int], days: int) -> int:
    def feasible(cap: int) -> bool:
        needed, load = 1, 0
        for w in weights:
            if load + w > cap:
                needed += 1
                load = 0
            load += w
        return needed <= days
    return first_true(max(weights), sum(weights) + 1, feasible)

The lower bound is max(weights), since the ship must carry the heaviest package. The upper bound is sum(weights), which ships everything in one day. Getting these bounds right is half the problem. The same skeleton solves “split array into k subarrays to minimize the largest sum.”

Variation 7: Count-based search over values

Find the k-th smallest element in an n×n matrix where each row and column is sorted. You can’t index into “the sorted order,” but you can count how many elements are at most v, with a staircase walk, in O(n). The predicate count_le(v) >= k is monotonic in v.

def kth_smallest(matrix: list[list[int]], k: int) -> int:
    n = len(matrix)

    def count_le(v: int) -> int:
        r, c, cnt = 0, n - 1, 0           # start at top-right corner
        while r < n and c >= 0:
            if matrix[r][c] <= v:
                cnt += c + 1               # whole row prefix is <= v
                r += 1
            else:
                c -= 1
        return cnt

    return first_true(matrix[0][0], matrix[-1][-1] + 1,
                      lambda v: count_le(v) >= k)

The smallest v with count_le(v) >= k is always an actual matrix element, so the answer is correct even though v ranges over every integer. Total cost is O(n log(max − min)).

Variations 5 to 7 share a recipe. Define the answer space, write a monotonic feasible or count predicate, and let first_true find the boundary. If you’ve worked through the two pointers vs fast/slow pointers guide or the sliding window practice problems, you’ll notice the feasibility checks are often those same linear scans, now wrapped in a log factor.

Phase 6: Practice Problems

Ordered easy to hard. Problem numbers are from LeetCode; double-check titles against the site before publishing.

Phase 7: Common Mistakes and Edge Cases

1. Mixing loop styles. If you write while lo <= hi but use hi = mid, the loop never terminates when lo == hi. Pick one shape (half-open [lo, hi), lo < hi, hi = mid / lo = mid + 1) and never mix them.

2. Wrong upper bound on the search space. In a half-open range, to include max(piles) as a candidate you pass max(piles) + 1. Forgetting the + 1 silently drops the largest candidate, and if the true answer is the max, you return the wrong thing.

3. Non-monotonic predicates. If your predicate flips back and forth, the search returns an arbitrary boundary with no error. Before coding, ask: “if this value works, does every larger value work?” For peak finding, the guarantee comes from the invariant, not the predicate.

4. Duplicates. Plain “find the element” returns some match. If you need the first or last, use lower or upper bound. In rotated arrays, duplicates break the a[i] <= a[-1] trick and can force O(n).

5. Empty input. first_true(0, 0, ...) returns 0, which is not a valid index in an empty array. Always check i < len(a) before reading a[i].

6. Integer overflow. Use lo + (hi - lo) / 2 in C++ and Java. This is the bug Bloch described in the JDK binary search.

7. Floating-point search. For real-valued answers, lo < hi can loop forever because mid may equal lo due to precision. Use a fixed iteration count (60 to 100 halvings is typically plenty for doubles) instead of an equality test.

8. Unsorted input. Binary search on unsorted data returns a wrong answer with no error. If you’re not sure the input is sorted, sort it first (O(n log n)) or reconsider the approach.

Phase 8: Where This Appears in Real Systems

git bisect. This is the Phase 1 problem made real. Per the Git documentation, the command uses a binary search algorithm to find the commit that introduced a bug, given a known good and a known bad commit. It checks out a commit in the middle and asks you to mark it good or bad, then repeats. The docs show output like “337 revisions left to test after this (roughly 9 steps),” which matches log₂(337) ≈ 8.4. You can automate the predicate with git bisect run <cmd>, where the script’s exit code says good or bad, and exit code 125 means “skip this commit” (for example, if it doesn’t build).

Standard libraries. Python’s bisect module and C++’s std::lower_bound / std::upper_bound / std::partition_point are production versions of Variations 1 and 2. They exist because hand-rolled binary search is easy to get wrong, so in real code you use these and keep your own template for interviews.

If your data lives in a tree rather than an array, the same halving idea shows up in the binary search tree implementation in C++.

Key Takeaways

• Binary search finds the boundary of a monotonic predicate, not just a value in a sorted array.
• Use one loop shape: half-open [lo, hi), hi = mid on True, lo = mid + 1 on False, return lo.
• Lower bound and upper bound solve first/last occurrence and counting, with no linear walk and no special cases for duplicates.
• “Minimum X such that it’s feasible” is search on the answer: write a feasible(x) check and search the range of possible answers.
• Correctness depends on monotonicity or an invariant, not sortedness. Verify it before coding.
• Most bugs come from loop-shape mixing, bad search bounds, empty input, and overflow, not from the core idea.
• Learn the library tools (bisect, std::lower_bound, git bisect) alongside the template.

FAQ

What are the main binary search patterns?
The common ones are lower bound, upper bound, rotated array search, peak finding, search on the answer, minimize-the-maximum, and counting-based search over a value range. They all reduce to finding the first True of a monotonic predicate.

How do I know when to use binary search on the answer?
Look for “minimum X so that it’s possible” or “minimize the maximum,” where checking a candidate is easy but finding the best is hard. If feasibility is monotonic (if X works, larger X works), binary search on the answer applies.

Does binary search work on unsorted arrays?
Usually no. It works when you have a monotonic predicate or a guaranteed invariant, as in rotated arrays or peak finding. For arbitrary unsorted data, you need to sort first or use a hash table.

Why use lo + (hi - lo) // 2 instead of (lo + hi) // 2?
In languages with fixed-width integers, lo + hi can overflow for very large arrays. Joshua Bloch described exactly this bug in a widely used JDK binary search. Python doesn’t overflow, but the habit carries over to C++ and Java.

What’s the time complexity of binary search on the answer?
It’s O(C × log R), where C is the cost of one feasibility check, and R is the size of the answer range. For Koko Eating Bananas, that’s O(n log M).