Binary Search cheatsheet

🔍 Binary Search

Turn the question into a predicate that flips once (F F F T T T), then halve the range until lo == hi.

Recognize the pattern

Sorted array + find a target, insertion point, or first/last occurrence → lower/upper bound (bisect_left / bisect_right).
The prompt demands O(log n) → it's binary search.
"Smallest X that still works" / "minimise the maximum" / "maximise the minimum" → binary search on the answer.
Huge answer range (up to 10^9) but checking one candidate is a cheap O(n) pass → binary search on the answer, O(n log R).
Sorted array that was rotated → compare nums[mid] with nums[-1] to find the rotation point.
Matrix whose rows continue one another in sorted order → search it as one flat list with divmod.
A yes/no question whose answer flips exactly once as x grows → the first-true template.

The one template: first True

Invariant: everything before lo is False, everything from hi on is True. hi may be one past the last candidate to mean "none". mid rounds down, so mid < hi and both branches shrink the range.

Python template

def first_true(lo: int, hi: int, pred) -> int:
    # pred looks like F F F T T T on [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid        # mid may be the answer
        else:
            lo = mid + 1    # answer is right of mid
    return lo               # hi if no True

Lower / upper bound and exact match

Python template

from bisect import bisect_left, bisect_right

def lower_bound(a: list[int], x: int) -> int:
    # first i with a[i] >= x  (== bisect_left)
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] >= x:
            hi = mid
        else:
            lo = mid + 1
    return lo

def index_of(a: list[int], x: int) -> int:
    i = lower_bound(a, x)
    return i if i < len(a) and a[i] == x else -1

# upper bound: first a[i] > x   -> bisect_right(a, x)
# count of x:  bisect_right(a, x) - bisect_left(a, x)
# last <= x:   bisect_right(a, x) - 1
# last < x:    bisect_left(a, x) - 1

Binary search on the answer

Minimise: first x where can(x) is True. Maximise: first x where can(x) is False, minus 1. lo = smallest sensible answer, hi = a value that surely works.

Python template

def min_feasible(lo: int, hi: int, can) -> int:
    # can(x): F F F T T T  (bigger x is easier)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def max_feasible(lo: int, hi: int, can) -> int:
    # can(x): T T T F F F  (bigger x is harder)
    hi += 1                 # room for "all True"
    while lo < hi:
        mid = (lo + hi) // 2
        if not can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo - 1

Rotated sorted array

nums[i] <= nums[-1] is F...F T...T; its first True is the minimum. Then lower-bound inside the run that can hold the target.

Python template

def rotation_point(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] <= nums[-1]:
            hi = mid
        else:
            lo = mid + 1
    return lo   # index of the minimum

# search: p = rotation_point(nums)
# target <= nums[-1] -> search [p, n)
# otherwise          -> search [0, p)

Sorted matrix as a flat list

Python template

def search_matrix(m: list[list[int]], t: int) -> bool:
    rows, cols = len(m), len(m[0])
    lo, hi = 0, rows * cols
    while lo < hi:
        mid = (lo + hi) // 2
        r, c = divmod(mid, cols)
        if m[r][c] >= t:
            hi = mid
        else:
            lo = mid + 1
    if lo == rows * cols:
        return False
    r, c = divmod(lo, cols)
    return m[r][c] == t

Operation costs

Operation	Time	Space
Search a sorted array (any bound)	O(log n)	O(1)
bisect_left / bisect_right	O(log n)	O(1)
bisect.insort into a list	O(n) (shifting)	O(1)
Binary search on the answer	O(n log R), R = range size	O(1)
Rotated array: min or search	O(log n)	O(1)
m × n sorted matrix as 1D	O(log(mn))	O(1)

Watch for

lo = mid with while lo < hi loops forever once hi == lo + 1. Use lo = mid + 1 and phrase the answer as a first True.
Forgetting "not found": start hi at len(nums) and after the loop check lo < len(nums) and nums[lo] == target.
Mixing conventions: closed [lo, hi] goes with while lo <= hi and hi = mid - 1; half-open [lo, hi) goes with while lo < hi and hi = mid. Pick one (half-open) and never mix.
Search-on-answer bounds: lo must not break the check (speed 0 → division by zero) and hi must surely be feasible (max pile, total sum).
Ceiling division: use (p + k - 1) // k, not math.ceil(p / k), which goes through floats.
Rotated arrays: compare with nums[-1] (works even when not rotated). With duplicates the guarantee drops to O(n) worst case.