Binary search, beyond sorted arrays

The mechanism behind binary search isn't really about arrays at all — it's about eliminating half of a search space on every comparison, which applies anywhere a monotonic condition exists.

Advanced

3 min read

The actual precondition, restated more generally

The lessons on Big-O framed binary search as requiring "sorted input" — more precisely, what it actually requires is a monotonic condition: a yes/no question over the search space that's False some prefix of the time and True for the rest (or vice versa), with a single clean boundary between them. A sorted array happens to be the simplest example — "is this element >= target" is False then True as you move left to right — but the same mechanism applies to anything with that shape, sorted array or not.

The template, once you see it that way

def binary_search(lo, hi, condition):
    # finds the smallest value in [lo, hi] where condition(value) is True,
    # given condition is False then True across the range
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid          # condition true here; answer could be mid or earlier
        else:
            lo = mid + 1      # condition false here; answer must be later
    return lo

Every binary search — on an array, on a range of numbers, on anything — is this same loop with a different condition. Once condition is defined correctly, the search itself never changes.

Searching a range of answers, not a range of indices

A common shape: instead of searching an array for a value, search the space of possible answers to a question, using a condition that's expensive to check but monotonic:

def min_speed_to_finish(piles, hours):
    def can_finish(speed):
        # True once speed is fast enough to eat every pile within `hours`
        return sum(-(-pile // speed) for pile in piles) <= hours
 
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

can_finish(speed) is False for every speed too slow to finish in time, then True for every speed at or above the minimum viable one — a monotonic condition over "possible eating speeds," not over array indices. Checking one speed costs O(n) (one pass over the piles), but binary searching over the range of speeds instead of trying every speed one by one turns a linear scan of the answer space into a logarithmic one — O(n log(max(piles))) instead of O(n · max(piles)).

Searching a rotated sorted array

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:              # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                    # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

A rotated sorted array (like [4,5,6,7,0,1,2]) isn't globally monotonic, but at every midpoint, at least one of the two halves is still a contiguous sorted run — the extra logic just figures out which half is the sorted one, then checks whether the target falls inside that half's range to decide which side to keep. The core idea — eliminate a half you can prove doesn't contain the answer — is unchanged; only the test for "which half to discard" gets more involved.

Why this generalization is worth internalizing

Recognizing "can I turn this into a monotonic yes/no question over some ordered space" is what turns binary search from "the algorithm for sorted arrays" into a tool that applies to an entire category of optimization problems — "find the minimum X such that Y holds" almost always binary-searches over X, provided checking Y for one candidate value of X is itself efficient.