Binary Search Patterns

Master binary search patterns in Python: lower and upper bounds, rotated sorted arrays, peak finding, 2D matrices and binary search on the answer.

• Intermediate
• 18 min read
• 4 objectives

Before this lessonLesson 2: Two Pointers and Sliding Window

The Searching lesson introduced binary search: halve the range each step and find an item in O(log n). In practice, the tricky problems rarely ask "is x in the list?". They ask for the first position that satisfies something, or they hide the sorted order inside a rotated array, a grid or a range of possible answers. This lesson gives you one template and shows how it covers all of them.

The mental model that makes everything click: binary search does not really search for a value. It searches for the boundary in a list of booleans that looks like False False False True True. If you can phrase your question as a condition that flips from false to true exactly once, binary search finds the flip point in O(log n).

One template: find the first True

Keep a half-open range [lo, hi). The answer is always inside it. Look at the middle; if the condition holds, the first True is at mid or earlier, so set hi = mid. Otherwise it is after mid, so set lo = mid + 1. When lo == hi, you have found it.

def first_true(lo, hi, cond):
    # smallest i in [lo, hi) with cond(i) True; returns hi if none
    while lo < hi:
        mid = (lo + hi) // 2
        if cond(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

scores = [12, 20, 20, 20, 35, 41, 58]
n = len(scores)
lower = first_true(0, n, lambda i: scores[i] >= 20)   # first 20
upper = first_true(0, n, lambda i: scores[i] > 20)    # first after the 20s
print("first index of 20:", lower)
print("count of 20:", upper - lower)
print("insert 40 at:", first_true(0, n, lambda i: scores[i] >= 40))

first index of 20: 1
count of 20: 3
insert 40 at: 5

Because the loop always shrinks the range and never skips the answer, there is no off-by-one guesswork and no infinite loop. Time O(log n), space O(1). Python's standard library has the same two searches built in: bisect_left is the lower bound and bisect_right the upper bound.

from bisect import bisect_left, bisect_right

scores = [12, 20, 20, 20, 35, 41, 58]
print(bisect_left(scores, 20), bisect_right(scores, 20))
print(bisect_left(scores, 99))   # past the end means "not present"

1 4
7

Rotated sorted arrays

A sorted list that has been rotated, like [40, 50, 60, 10, 20, 30], is no longer sorted, but it still has a monotonic condition: "is this element less than or equal to the last element?" is False for the left part and True for the right part. The first True is the minimum, which is also the rotation point.

# from earlier in this lesson
def first_true(lo, hi, cond):
    # smallest i in [lo, hi) with cond(i) True; returns hi if none
    while lo < hi:
        mid = (lo + hi) // 2
        if cond(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

scores = [12, 20, 20, 20, 35, 41, 58]

# new code
def rotation_point(nums):
    last = nums[-1]
    return first_true(0, len(nums), lambda i: nums[i] <= last)

def search_rotated(nums, target):
    k = rotation_point(nums)
    # pick the sorted half that could contain target
    if target <= nums[-1]:
        lo, hi = k, len(nums)
    else:
        lo, hi = 0, k
    i = first_true(lo, hi, lambda j: nums[j] >= target)
    return i if i < len(nums) and nums[i] == target else -1

temps = [40, 50, 60, 10, 20, 30]
print("min at", rotation_point(temps))
print(search_rotated(temps, 50), search_rotated(temps, 20), search_rotated(temps, 35))

min at 3
1 4 -1

Two O(log n) searches in a row is still O(log n). Splitting a tricky problem into "find the structure, then search the easy part" is a habit worth building.

Peak finding

A peak is an element bigger than its neighbours. The list is not sorted at all, yet binary search still works: if nums[mid] < nums[mid + 1], you are on an uphill slope, and there must be a peak to the right. The condition "nums[i] > nums[i + 1]" is guaranteed to become True somewhere, and the first place it does is a peak.

# from earlier in this lesson
def first_true(lo, hi, cond):
    # smallest i in [lo, hi) with cond(i) True; returns hi if none
    while lo < hi:
        mid = (lo + hi) // 2
        if cond(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

scores = [12, 20, 20, 20, 35, 41, 58]

# new code
def find_peak(nums):
    return first_true(0, len(nums) - 1, lambda i: nums[i] > nums[i + 1])

traffic = [3, 9, 14, 22, 18, 7, 11, 4]
p = find_peak(traffic)
print(p, traffic[p])

3 22

Note the condition is not monotonic over the whole list (the hill at index 6 means it goes False again), but the search still returns a valid peak because each step keeps a range that must contain one. This is the sort of reasoning interviewers want to hear.

Searching a sorted 2D matrix

If every row of a matrix is sorted and each row starts after the previous one ends, the whole grid is one sorted list laid out row by row. Map a flat index i to (i // cols, i % cols) and search as normal.

# from earlier in this lesson
def first_true(lo, hi, cond):
    # smallest i in [lo, hi) with cond(i) True; returns hi if none
    while lo < hi:
        mid = (lo + hi) // 2
        if cond(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

scores = [12, 20, 20, 20, 35, 41, 58]

# new code
def search_matrix(grid, target):
    rows, cols = len(grid), len(grid[0])
    cell = lambda i: grid[i // cols][i % cols]
    i = first_true(0, rows * cols, lambda i: cell(i) >= target)
    return i < rows * cols and cell(i) == target

grid = [[1, 4, 7, 9],
        [12, 15, 18, 21],
        [30, 33, 36, 40]]
print(search_matrix(grid, 18), search_matrix(grid, 19))

True False

Time O(log(rows * cols)), space O(1).

Binary search on the answer

The most powerful pattern: when the question asks for the smallest value that works, and "works" is monotonic (if 10 works, 11 also works), binary search over the possible answers and write a feasible(x) check. Example: stackcone has video files of given sizes that must be uploaded in order over d days. What is the smallest daily upload capacity that finishes in time?

# from earlier in this lesson
def first_true(lo, hi, cond):
    # smallest i in [lo, hi) with cond(i) True; returns hi if none
    while lo < hi:
        mid = (lo + hi) // 2
        if cond(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

scores = [12, 20, 20, 20, 35, 41, 58]

# new code
def days_needed(sizes, cap):
    days, load = 1, 0
    for s in sizes:
        if load + s > cap:
            days += 1
            load = 0
        load += s
    return days

def min_capacity(sizes, d):
    lo, hi = max(sizes), sum(sizes) + 1
    return first_true(lo, hi, lambda cap: days_needed(sizes, cap) <= d)

sizes = [7, 2, 5, 10, 8]
print(min_capacity(sizes, 2))
print(min_capacity(sizes, 3))

18
14

The answer range is from the largest single file (you must fit it in one day) to the total. Each check is O(n), and there are O(log S) checks where S is the sum, so the total is O(n log S) time and O(1) space. The same shape solves "minimum eating speed", "split array largest sum" and many scheduling problems.

Recap

• Binary search finds the boundary where a condition flips from False to True.
• One half-open first_true template covers lower bound, upper bound and insert position.
• Rotated arrays and peaks are not sorted but still have a condition you can halve on.
• A sorted 2D matrix is a flat sorted list with index maths.
• Binary search on the answer turns "minimum value that works" into O(log range) feasibility checks.

# Write your solution here