Search Patterns

Plain binary search finds one value in a sorted array. But the move underneath it — throw away half the possibilities with every step — is far more general than that one setting.

It works wherever a property is monotonic: where the answer, as you slide along the input, only ever moves in one direction and never doubles back. Once you learn to spot that shape, binary search starts showing up in places that have no sorted array in sight. Let us walk four of them.

Counting copies with bisect_left and bisect_right

Given a sorted list with duplicates, you often want the first copy of a value, the last, or simply how many. Python’s bisect answers all three with two lookups.

Think of bisect_left(a, x) as asking “where does the run of xs begin?” and bisect_right(a, x) as “where does it end?” — more precisely, the leftmost and the just-past-the-rightmost spot where x could sit without disturbing the order.

from bisect import bisect_left, bisect_right

a = [1, 2, 2, 2, 3, 4, 4, 5]

lo = bisect_left(a, 2)        # start of the run of 2s
hi = bisect_right(a, 2)       # one past the end of that run

print("first index of 2:", lo)
print("last index of 2 :", hi - 1)
print("count of 2       :", hi - lo)
print("count of 6       :", bisect_right(a, 6) - bisect_left(a, 6))

first index of 2: 1
last index of 2 : 3
count of 2       : 3
count of 6       : 0

The count is just bisect_right - bisect_left, and a value that is absent gives the same index twice, so its count comes out as zero. This shows up constantly in time-series work — bucketing a timestamp into sorted interval boundaries, or counting events inside a window — and every call is O(log n).

Searching a rotated sorted array

Now a sorted array that has been rotated at some pivot, like [4, 5, 6, 7, 0, 1, 2]. Comparing the target with the middle element no longer tells you which way to go — the target could be on either side of the break. So how can binary search still apply?

Here is the saving observation. However you cut a rotated array in half, at least one half is still in perfect order. If you can tell which half is sorted, you can check whether the target falls inside that orderly half — and if it does not, it must be in the other one. That is enough to make a confident decision every step.

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

a = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(a, 0))   # present
print(search_rotated(a, 3))   # absent

4
-1

The rotation hid the global order, but one half is always intact — and that is all binary search needs to keep its O(log n) speed.

Walking a sorted matrix

Picture a grid where every row climbs left-to-right and every column climbs top-to-bottom. We want to find 5.

Where should we stand? Not a corner where both directions go the same way — the top-left only grows, the bottom-right only shrinks, so neither gives a clear choice. The top-right corner is special: from there, stepping left always decreases the value and stepping down always increases it. That is exactly the “higher or lower” signal binary search feeds on.

Each step deletes an entire row or an entire column, so the whole walk is O(m + n):

def search_matrix(matrix, target):
    row, col = 0, len(matrix[0]) - 1          # start at the top-right
    while row < len(matrix) and col >= 0:
        val = matrix[row][col]
        if val == target:
            return True
        elif val > target:
            col -= 1                          # too big — drop this column
        else:
            row += 1                          # too small — drop this row
    return False

m = [
    [ 1,  4,  7, 11],
    [ 2,  5,  8, 12],
    [ 3,  6,  9, 16],
    [10, 13, 14, 17],
]
print(search_matrix(m, 5))    # present
print(search_matrix(m, 20))   # absent

True
False

Searching the answer itself

This is the most powerful turn of the idea. Sometimes there is no sorted list of candidates to search at all. Instead you binary-search the range of possible answers: you guess a value in the middle, ask “is this good enough?”, and let the answer to that question tell you which way to move.

Take a real one. A ship carries packages, in order, and can load at most C kilograms a day. Given the package weights, what is the smallest daily capacity C that gets everything shipped within D days?

The answer must lie between max(weights) — you cannot carry a package heavier than the ship’s daily limit — and sum(weights) — enough to ship everything in a single day. And the test “does capacity C finish within D days?” is monotonic: if some C works, every larger C works too. A monotonic yes/no over a numeric range is precisely what binary search needs.

def ship_within_days(weights, D):
    def days_needed(capacity):
        days, load = 1, 0
        for w in weights:
            if load + w > capacity:
                days += 1                      # start a new day
                load = 0
            load += w
        return days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= D:
            hi = mid                           # feasible — try a smaller ship
        else:
            lo = mid + 1                       # too slow — needs a bigger ship
    return lo

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(ship_within_days(weights, 5))   # fewest days allowed
print(ship_within_days(weights, 1))   # everything in one day

15
55

The same shape fits a surprising range of questions: the smallest model threshold that still passes a quality bar, the least bandwidth that serves requests inside a latency budget, the fewest machines that finish a job in time. Whenever the question is “what is the smallest X that is enough?” and “enough” never un-happens as X grows, you can binary-search it.

Practice