Binary Search, Binary Search on the Answer, and Ternary Search

Binary search is not just "find x in a sorted array". It finds the boundary of any yes/no condition that flips exactly once over an ordered range, using O(log n) checks. That one idea covers lower and upper bounds, rotated arrays, peaks, square roots, and the very common "binary search on the answer" pattern for minimizing a maximum or maximizing a minimum. Most bugs come from mixing different templates, so learn one template with a clear invariant and reuse it everywhere.

Intuition

Suppose a predicate pred(x) over integers in [lo, hi) looks like False False ... False True True ... True. We want the first True. Keep this invariant:

• everything left of lo is known to be False,
• everything at or right of hi is known to be True (or is past the end).

Check the middle. If pred(mid) is True, the first True is at mid or before it, so set hi = mid. Otherwise mid and everything before it are False, so set lo = mid + 1. The range shrinks every step, and when lo == hi that position is the answer (if it equals the original hi, nothing is True).

Every other binary search is this template with a different predicate:

• Lower bound (first index with a[i] >= x) and upper bound (first index with a[i] > x).
• Binary search on the answer: when the question is "the minimum value v such that something is feasible", and feasibility is monotone (if v works, every larger v works too), binary search over v and test feasibility with a greedy check.
• Maximize a minimum: feasibility is True then False; find the first False and step back one.
• Real numbers: same loop, but stop after a fixed number of halvings.

If a function first increases and then decreases (unimodal), its maximum is found either by binary searching on the slope (f(i) > f(i + 1) flips once) or with ternary search, which compares two interior points and discards a third of the range each step.

When to use it in interviews / OAs

• The input is sorted, or sorted after a rotation, and you need O(log n).
• The statement asks for the minimum speed, capacity, time, or largest-sum bound such that a plan works, or the maximum minimum distance or size. Constraints with answers up to 10^9 or 10^18 are a strong hint.
• You can easily test "is the answer at most v?" in O(n), but cannot compute the answer directly.
• Counting questions such as "k-th smallest value in a sorted matrix or multiplication table": binary search on the value and count how many entries are at most it.
• Maximizing a unimodal function, or finding a peak.

Template

The core: first index where the predicate becomes True

from typing import Callable


def first_true(lo: int, hi: int, pred: Callable[[int], bool]) -> int:
    """Smallest x in [lo, hi) with pred(x) True, for pred shaped False...False True...True.
    Returns hi when pred is False everywhere."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid      # mid may be the answer: keep it
        else:
            lo = mid + 1  # mid and everything before it are False
    return lo

Bounds in a sorted array

Python's bisect_left and bisect_right are exactly lower bound and upper bound:

from bisect import bisect_left, bisect_right


def search_range(nums: list[int], target: int) -> list[int]:
    """First and last index of target in a sorted list, or [-1, -1]."""
    left = bisect_left(nums, target)  # first index with nums[i] >= target
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    return [left, bisect_right(nums, target) - 1]  # bisect_right: first index with nums[i] > target

The number of occurrences of x is bisect_right(a, x) - bisect_left(a, x), and the count of values in [lo, hi] is bisect_right(a, hi) - bisect_left(a, lo).

Binary search on the answer: minimize the maximum

Ship packages in order within days days; find the smallest ship capacity that works. A larger capacity never needs more days, so fits is monotone:

def min_ship_capacity(weights: list[int], days: int) -> int:
    def fits(cap: int) -> bool:  # greedy: fill each day until the next package would overflow
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used += 1
                load = 0
            load += w
        return used <= days

    # the answer lies in [max(weights), sum(weights)]
    return first_true(max(weights), sum(weights) + 1, fits)

Maximize the minimum

Place m items at distinct positions so that the smallest gap between neighbors is as large as possible. can(gap) is True for small gaps and False for large ones, so search for the first False and step back:

def max_min_distance(positions: list[int], m: int) -> int:
    pos = sorted(positions)

    def can(gap: int) -> bool:  # greedy: take every position that is far enough from the last one
        count, last = 1, pos[0]
        for p in pos[1:]:
            if p - last >= gap:
                count += 1
                last = p
        return count >= m

    return first_true(1, pos[-1] - pos[0] + 2, lambda g: not can(g)) - 1

Rotated sorted array

In a rotated array of distinct values, nums[i] <= nums[-1] is False on the left (larger) block and True on the right block, so the template finds the minimum. Then search the half that can contain the target:

def search_rotated(nums: list[int], target: int) -> int:
    if not nums:
        return -1
    n = len(nums)
    pivot = first_true(0, n, lambda i: nums[i] <= nums[-1])  # index of the minimum
    lo, hi = (pivot, n) if target <= nums[-1] else (0, pivot)
    i = bisect_left(nums, target, lo, hi)
    return i if i < hi and nums[i] == target else -1

Peaks: binary search on the slope

Treat positions outside the array as minus infinity. "The array goes down after i" (nums[i] > nums[i + 1]) must flip from False to True somewhere, and any such flip is a peak. On a unimodal array it is the maximum:

def find_peak(nums: list[int]) -> int:
    """Index of an element larger than its neighbors; adjacent values must differ."""
    return first_true(0, len(nums) - 1, lambda i: nums[i] > nums[i + 1])

Real-valued search and ternary search

With real numbers there is no "mid + 1". Halve the interval a fixed number of times instead of looping until hi - lo < eps, which can spin forever because of rounding:

def cube_root(x: float) -> float:
    """Cube root for |x| up to about 1e18, so the starting interval is at most that wide."""
    lo, hi = min(-1.0, x), max(1.0, x)  # the root lies in this interval
    for _ in range(100):  # 100 halvings shrink the interval by 2^100, about 1e30
        mid = (lo + hi) / 2
        if mid * mid * mid >= x:  # plain multiplication gives inf on overflow instead of raising
            hi = mid
        else:
            lo = mid
    return hi


def ternary_max(f: Callable[[float], float], lo: float, hi: float) -> float:
    """Argmax of a strictly unimodal function on [lo, hi]."""
    for _ in range(200):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1  # the peak is not left of m1
        else:
            hi = m2  # the peak is not right of m2
    return (lo + hi) / 2

The final precision is the starting width divided by 2^100, so an interval of width 1e18 still ends within about 1e-12; for wider ranges, tighten the starting bounds or raise the iteration count. Golden-section search is a refinement of ternary search that reuses one probe per step; it only matters when evaluating f is expensive.

Complexity

• Searching n positions: O(log n) predicate checks, O(1) extra space for the iterative version.
• Binary search on the answer over a range of size R with an O(n) check: O(n log R). For capacities up to 10^9 that is about 30 checks.
• Real-valued search and ternary search: O(iterations * cost of f).
• bisect functions are O(log n) comparisons, but inserting into a Python list with insort is O(n) because of shifting.

Common pitfalls

• Infinite loops. With while lo < hi, use mid = (lo + hi) // 2 together with hi = mid and lo = mid + 1. Pairing lo = mid with a floor midpoint never terminates when hi = lo + 1.
• Mixing templates. Closed [lo, hi] with while lo <= hi and half-open [lo, hi) with while lo < hi are both fine; mixing their updates is not. Write down what lo and hi mean.
• Wrong search range. The range must contain the answer: ship capacity starts at max(weights) (otherwise the heaviest package never fits), and the upper end must be feasible.
• Non-monotone predicates. Check that "v works" really implies "v + 1 works" (or the reverse) before binary searching.
• Overflow in C++ or Java: compute lo + (hi - lo) / 2, and use 64-bit types when the check sums large values.
• Returning the wrong side in max-min problems: the answer is the last True, which is the first False minus one.
• Duplicates in rotated arrays break the nums[i] <= nums[-1] split; with duplicates the worst case becomes O(n) (shrink the range by one when the ends are equal).
• Ternary search on plateaus. Equal values on both probes make it unable to tell which side the peak is on; it needs strict unimodality.

Interview variations

• Find first and last position, search insert position, count occurrences: bisect.
• Integer square root: first_true(0, x + 2, lambda v: v * v > x) - 1.
• Minimum speed / capacity / days (eating bananas, shipping packages, making bouquets), split an array to minimize the largest sum: minimize the maximum with a greedy check.
• Magnetic balls / placing routers / aggressive cows: maximize the minimum gap.
• Rotated sorted array: find the minimum, search for a target, handle duplicates.
• K-th smallest in a sorted matrix or multiplication table: binary search on the value, count entries at most it in O(n).
• Median of two sorted arrays: binary search on how many elements to take from the shorter array, O(log min(m, n)).
• Time-based key-value store and find k closest elements: bisect over sorted timestamps or window starts.
• Peak element and maximum of a bitonic array: binary search on the slope.