Binary Search

The idea

If one comparison rules out half the candidates, you find the answer in O(log n). The classic case is a sorted array, but the real power is searching any monotonic condition — “find the boundary where false flips to true.”

The exact-match template

A half-open [lo, hi) range with a single invariant avoids off-by-one bugs:

def search(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] == target: return mid
        if nums[mid] < target:  lo = mid + 1
        else:                   hi = mid
    return -1

The unifying model: boundary of a predicate

Most binary-search problems are “find the first index where pred(i) is true,” where pred is monotonic (false…false, true…true):

def first_true(lo, hi, pred):           # pred False on [lo,k), True on [k,hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid): hi = mid          # true → answer is here or left
        else:         lo = mid + 1      # false → answer is right
    return lo                           # the first index where pred holds

This single function gives:

• lower_bound (first index with nums[i] >= target) and upper_bound (> target) → first/last occurrence and counts of a value in a sorted array.
• Find min in rotated sorted array — pred(i) = nums[i] <= nums[-1].
• Any “smallest/largest value satisfying a monotonic condition.”

Deciding first-true vs last-true up front (and the matching boundary update) is the whole game.

Binary search on the answer (parametric search)

When the answer is a number and “is value X feasible?” is monotonic (feasible above/below a threshold), binary-search the threshold — even with no array in sight:

import math
def min_eating_speed(piles, h):
    def hours(speed): return sum(math.ceil(p / speed) for p in piles)
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h: hi = mid    # feasible → try slower
        else:               lo = mid + 1
    return lo

Solves Koko Eating Bananas, Capacity to Ship Packages in D Days, Split Array Largest Sum, Minimize Max Distance — anywhere “minimize the max / maximize the min subject to a feasibility check.” The check is often O(n), giving O(n log range) overall.

Rotated and 2-D variants

• Search in rotated sorted array — at each step, one half is sorted; check whether the target lies in the sorted half to decide direction. O(log n).
• Find peak element — move toward the higher neighbor; a peak must exist. O(log n) on an unsorted array.
• Search a 2-D matrix — treat a row-sorted matrix as one sorted array (index math), or staircase-search from a corner.

Binary search on floats

For continuous answers (e.g. “minimum radius”), loop a fixed number of iterations or until the range is within eps:

while hi - lo > 1e-6:
    mid = (lo + hi) / 2
    if feasible(mid): hi = mid
    else:             lo = mid

Pitfalls

• Infinite loops — ensure the range strictly shrinks every iteration (the lo = mid + 1 vs hi = mid split matters).
• First vs last occurrence — they use different boundary updates; pick deliberately.
• Mid overflow — lo + (hi - lo) // 2 in languages with fixed ints (not Python).
• Wrong monotonicity — binary-search-on-answer only works if feasibility is monotonic; verify it.

Choosing in an interview

• Sorted array, find a value / first-or-last occurrence → boundary template.
• “Minimize the maximum / maximize the minimum” with a feasibility check → binary search on the answer.
• Rotated / peak / 2-D → the variants (one sorted half / go uphill / index math).

Reframe almost everything as “find the first index where a monotonic predicate becomes true” — one template, fewer bugs.