Binary search (and binary search on the answer)

Halve the space each step. log2(10⁹) ≈ 30 comparisons. The idea is never the hard part — getting the boundaries right so you neither loop forever nor go off-by-one is. So we pick ONE template and reuse it everywhere.

Why this pattern

Any time the search space is monotonic — once a property flips it stays flipped — you can throw away half of it per comparison. The hard part of binary search is never the idea; it's getting the boundaries right. So we standardize on a single template and treat everything else as a thin wrapper around it.

The mental model: find the boundary, not the value

Reframe every binary search as: "I have a predicate P(i) that is False, False, …, False, True, True, …, True over the index range. Find the FIRST index where it becomes True." That single primitive (lower_bound) expresses everything:

This is why we lead with lower_bound / upper_bound: they ARE the boundary primitive.

The canonical, safe template (half-open [lo, hi))

lo, hi = 0, n            # hi is EXCLUSIVE: search range is [lo, hi)
while lo < hi:
    mid = lo + (hi - lo) // 2     # never overflows; biased low
    if P(mid):
        hi = mid         # mid might be the answer; keep it in range (right half dropped)
    else:
        lo = mid + 1     # mid is definitely not; discard it
return lo                # lo == hi == first index where P is True (or n)

The boundary primitives (written by hand)

lower_bound

First index i with a[i] >= target (== Python's bisect_left). Predicate P(i) := a[i] >= target (False…False True…True).

def lower_bound(a: List[int], target: int) -> int:
    lo, hi = 0, len(a)               # half-open [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] >= target:
            hi = mid                 # mid satisfies P; it may be THE first one
        else:
            lo = mid + 1             # mid fails P; throw it away
    return lo

upper_bound

First index i with a[i] > target (== Python's bisect_right). Predicate P(i) := a[i] > target.

def upper_bound(a: List[int], target: int) -> int:
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    return lo

LeetCode 704 — Binary Search (exact)

Return index of target, else -1. Find lower_bound, then verify the landed element equals target. Reusing the boundary primitive avoids a bespoke, bug-prone loop.

def binary_search_exact(a: List[int], target: int) -> int:
    i = lower_bound(a, target)
    return i if i < len(a) and a[i] == target else -1

LeetCode 34 — First and Last Position of Element in Sorted Array

First occurrence = lower_bound(target); last occurrence = upper_bound(target) - 1. If lower_bound lands outside the array or on a non-target, the value is absent.

def search_range(a: List[int], target: int) -> List[int]:
    lo = lower_bound(a, target)
    if lo == len(a) or a[lo] != target:
        return [-1, -1]
    hi = upper_bound(a, target) - 1
    return [lo, hi]

Classic variants on a sorted-ish array

LeetCode 33 — Search in Rotated Sorted Array (distinct values)

Even after rotation, at least ONE half [lo..mid] or [mid..hi] is still sorted. Detect which half is sorted (compare endpoints), then test whether target lies within that sorted half's range; if so search it, else search the other half. Each step still halves the space. (This variant uses an inclusive [lo, hi] range because we return on an exact hit.)

def search_rotated(a: List[int], target: int) -> int:
    lo, hi = 0, len(a) - 1           # inclusive here; we return on exact hit
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:                      # left half [lo..mid] is sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1                     # target inside the sorted left
            else:
                lo = mid + 1
        else:                                    # right half [mid..hi] is sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1                     # target inside the sorted right
            else:
                hi = mid - 1
    return -1

LeetCode 162 — Find Peak Element

Return ANY index i with a[i] greater than both neighbors (a[-1] and a[n] treated as -inf), in O(log n). There's no global sort, but the slope gives monotonic guidance. If a[mid] < a[mid+1] the array is rising, so a peak must lie to the RIGHT (you'll eventually descend or hit the boundary). Otherwise a peak is at mid or to the left. We binary-search the "is the next step uphill?" predicate.

def find_peak_element(a: List[int]) -> int:
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < a[mid + 1]:
            lo = mid + 1     # uphill to the right: peak is strictly right of mid
        else:
            hi = mid         # mid >= mid+1: a peak is at mid or to its left
    return lo

Binary search on the answer (the high-value generalization)

Sometimes the array isn't what's sorted — the ANSWER SPACE is monotonic. If feasible(x) is False for small x and True for large x (or vice versa), binary search the answer x directly. Trigger signals in a problem statement:

• "minimum/maximum X such that …" or "smallest capacity / largest k …"
• a feasibility check feasible(x) you can compute in O(n)
• and feasible is MONOTONIC in x (more capacity/time can never make a feasible plan infeasible).

Total cost: O(n · log(range)).

The generic answer-space search

def search_first_true(lo: int, hi: int, feasible: Callable[[int], bool]) -> int:
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

LeetCode 875 — Koko Eating Bananas

Smallest integer speed k so Koko eats all piles within h hours (each pile takes ceil(pile / k) hours). hours_needed(k) DECREASES as k increases — so "can finish in h hours at speed k" is monotonic in k: False for tiny k, then True forever. Binary search the smallest feasible k in [1, max(pile)].

def min_eating_speed(piles: List[int], h: int) -> int:
    def feasible(k: int) -> bool:
        # ceil(p/k) without floats: (p + k - 1)//k
        hours = sum((p + k - 1) // k for p in piles)
        return hours <= h
    return search_first_true(1, max(piles), feasible)

LeetCode 1011 — Capacity To Ship Packages Within D Days

Smallest ship capacity so packages (in order) ship within days days. A bigger capacity can never need MORE days, so days_needed(cap) is monotonically non-increasing ⇒ "ships within days" flips False→True once. Lower bound on capacity is max(weight) (must fit the heaviest item); upper bound is sum(weights) (one day). Search that range.

def ship_within_days(weights: List[int], days: int) -> int:
    def feasible(cap: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > cap:           # start a new day
                d += 1
                load = 0
            load += w
        return d <= days
    return search_first_true(max(weights), sum(weights), feasible)

LeetCode 69 — Sqrt(x)

Floor of the square root, integer arithmetic. The predicate mid*mid > x is monotonic. Find the first mid where it's True; the answer (floor sqrt) is one below that boundary.

def int_sqrt(x: int) -> int:
    if x < 2:
        return x
    # first m in [0, x] with m*m > x; floor-sqrt is that boundary minus 1
    first_too_big = search_first_true(0, x, lambda m: m * m > x)
    return first_too_big - 1

Spot-checks: min_eating_speed([3,6,7,11], 8) == 4, ship_within_days([1..10], 5) == 15, and int_sqrt(2147395600) == 46340 — and the hand-written lower_bound / upper_bound agree with bisect.bisect_left / bisect_right across every target.