Binary Search (and Variants)

Everyone learns binary search as "find a number in a sorted array by halving," and then most people underuse it for the rest of their careers, because that framing hides the real idea. The real idea is this: if you can ask a yes-or-no question whose answer flips exactly once as you move along a range, from all-no to all-yes, then you can find the flip point in O(log n) questions instead of O(n). The sorted array is just the most obvious place that flip lives. Once you see the pattern as "find the boundary of a monotonic condition," it starts showing up everywhere.

The textbook version

Start with the familiar case to fix the mechanics. In a sorted array, the question "is arr[mid] less than the target" flips from yes to no at exactly the spot the target belongs, so each comparison lets you discard half the remaining range.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2       # avoids overflow in languages that can
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Twenty questions, not twenty thousand: a million-element array is searched in about twenty steps. The lo + (hi - lo) // 2 habit is worth keeping even in Python, where integers do not overflow, because the moment you port the idea to a language where they do, that is the line that saves you.

The sorted array 1 3 5 7 9 11 13 15 searched for 11: step one checks the middle value 7, which is smaller, so the whole left half is discarded and the search moves right; step two checks 11 and finds it, with each comparison halving the remaining range.

In the wild: git bisect

Here is the version that changes how you think. You have a bug that was not there fifty commits ago and is there now, and you want the exact commit that introduced it. Checking commits one by one is a linear slog. But notice the structure: the commits form a sequence that is "good, good, good, ..., broken, broken," flipping exactly once. That is a sorted array in disguise, and the "comparison" is just building that commit and testing it. Binary search finds the culprit in about log n builds. This is precisely what git bisect automates.

Eight commits in order, the first four good and the last four bad, so the predicate is-bad flips exactly once between index three and four; because the flip is monotonic, binary search finds that first bad commit in about log n builds, which is exactly what git bisect does.

def first_bad_commit(commits, is_bad):
    # commits are in chronological order; is_bad(commit) -> True once the bug exists
    lo, hi = 0, len(commits) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_bad(commits[mid]):
            hi = mid              # the culprit is mid or earlier, keep it in range
        else:
            lo = mid + 1          # mid is clean, the flip is later
    return commits[lo]

Nothing here is a number in a sorted list, yet it is exactly binary search, because is_bad is monotonic: once a commit is bad, every later one is too. That monotonic yes-or-no is the only thing binary search ever actually needed. The same move, called "binary search on the answer," solves a whole class of optimization problems: the least ship capacity that delivers all packages in D days, the smallest feasible budget, the minimum k that satisfies a constraint. You binary-search the answer space and let a feasibility check play the role of the comparison.

Notice too that this variant finds the first commit that satisfies the condition, not just any match. That leftmost-boundary shape, moving hi to mid rather than mid - 1, is the same one that powers lower-bound and upper-bound searches over duplicates.

Both shapes are runnable in the DSA Lab: the "search on the answer" mode probes a hidden F..F T..T strip exactly like bisect probes commits, and the "Lower bound" mode is that leftmost-boundary variant over duplicates.

$ ./dsa-lab --embed
DSA Lab

Interactive playground for algorithm patterns: two pointers and sliding windows on a scrubbable timeline, binary search and search-on-the-answer, sorting comparison (6 algorithms), trees (BST, AVL, Heap, Trie), graph algorithms (Cycle Detection, MST, SCC, Max Flow) and hash collision strategies. Every configuration is deep-linkable.

# Eight candidates with the predicate flipping at the fifth, exactly like the eight commits above. Each probe rules out half the rest: count them against the linear alternative.

The trigger

The data is sorted, or there is a monotonic yes-or-no you could ask, and you want a position, a boundary, or the smallest or largest value that works. The giveaway for the advanced form is a problem asking for a minimum or maximum "such that" something holds: if you can write a feasibility check that flips once, you can binary-search the answer.

Where it shows up

  • Plain lookup in sorted data, and the lower-bound and upper-bound variants for the first or last occurrence among duplicates.
  • Rotated sorted arrays, where one extra comparison decides which half is still in order.
  • Binary search on the answer: minimum capacity, minimum time, smallest threshold, any monotonic feasibility question.

Where it bites

Binary search is famously easy to get subtly wrong, and the bugs are always at the edges. lo <= hi versus lo < hi, and whether a branch moves to mid, mid + 1, or mid - 1, determines whether the loop terminates and whether it lands on the right side of the boundary. A single wrong choice yields an infinite loop or an off-by-one that only shows up on the first or last element. Decide up front whether you are finding an exact match or a boundary, and keep the interval definition consistent with that.

When it is the wrong tool

The prerequisite is order or monotonicity, and without it binary search returns confident garbage. If the data is unsorted and you only need one lookup, sorting first at O(n log n) is worse than a single O(n) scan, and a hash set answers membership in O(1) regardless. If the condition you are searching is not actually monotonic, the whole premise collapses and you will get a plausible wrong answer, which is worse than an obvious one. And if the collection changes constantly, keeping an array sorted costs O(n) per insertion, so a balanced tree or hash structure is usually the better home.

Its neighbors

It is Divide & Conquer at its most minimal, discarding a half rather than solving both. On a sorted array it often competes with Two Pointers, and knowing which the problem rewards is worth a moment's thought. And it frequently teams up with Sorting-Based Patterns, since the sort is what earns the O(log n) lookups that follow.

References