Binary Search

Back to Index

Use when: searching in a sorted space, or when the answer space is monotonic (if X works, X-1 also works).

Signal words: sorted array, find minimum/maximum that satisfies condition, O(log n) required.

Core Idea

Reframe as: minimize k such that condition(k) is True.

Template (generalized)

def binary_search(arr):
    def condition(value) -> bool:
        pass  # define your condition
 
    left, right = 0, len(arr)  # set boundary to include all candidates
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid       # mid could be answer, shrink right
        else:
            left = mid + 1    # mid definitely not answer, move left up
    return left               # left == right == first index where condition is True

Setup Checklist

1. What is the search space? (index range, value range, answer range)
2. What is the condition? (monotonic - once true, stays true)
3. Return left or left - 1? (left = first True, left - 1 = last False)

Common Variants

• Search in rotated sorted array: check which half is sorted first
• Binary search on answer: search the value space, not index space

---

Problems Using This Pattern