Binary Search

What it is

Binary search finds a target or a boundary by repeatedly discarding half of an ordered search space. Instead of checking every candidate, it uses one comparison to determine which half can still contain the answer.

In a sorted array of length n, direct scanning takes O(n) time. Binary search takes O(log n) comparisons because the remaining interval shrinks by roughly half each iteration.

The deeper requirement is monotonicity, not necessarily a sorted array. If a predicate is false for every candidate before some boundary and true for every candidate afterward, binary search can find the first true candidate. Reversing the pattern lets it find the last true candidate.

This extends the technique to optimization: search possible answers, and test whether each proposed answer is feasible. The difficult part is often designing and proving the feasibility check, not writing the search loop.

How to recognize it

Look for these signals:

• A sorted array, sorted timestamps, or an ordered range of integers.
• Requests for the first value at least a threshold, the last value below a threshold, or the insertion position of a value.
• Many independent queries against the same sorted data. Each query can use its own threshold without changing the array.
• A request to minimize the largest cost or maximize the smallest distance.
• A candidate limit that becomes easier to satisfy as it increases, or a candidate requirement that becomes harder.
• A ranked item whose position can be measured by counting items up to a candidate value.
• A large answer range that is impossible to scan, but whose midpoint can be evaluated efficiently.

An optimization objective alone is not enough. First explain why feasibility changes direction at most once.

The core technique

1. Exact lookup and sorted boundaries

For exact lookup, maintain a closed interval [lo, hi] containing every remaining possible index:

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

With duplicates, this returns an arbitrary matching index. Boundary search is preferable when the first or last occurrence matters.

A lower bound is the first index whose value is at least the target. An upper bound is the first index whose value is strictly greater than the target. Both may return len(a).

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

Here [lo, hi) is the unresolved interval. Everything before lo is too small; everything at or beyond hi satisfies the threshold.

Change < target to <= target to obtain upper bound. The number of occurrences is upper_bound - lower_bound; the last occurrence is upper_bound - 1, after checking that the target exists.

For independently shifted time thresholds, compute each threshold and perform a fresh lower-bound query. In Python, bisect_left and bisect_right provide these operations.

2. Binary search on the answer

Use this variant when candidates are numeric answers and a decision procedure can test each candidate.

def first_true(lo, hi, feasible):
    # Inclusive range; requires feasible(hi) to be true.
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

To minimize a limit, seek the first feasible value. To maximize a requirement, seek the last feasible value. A last-true search uses the upper midpoint (lo + hi + 1) // 2, keeping lo = mid when feasible; this prevents stalling when two candidates remain.

Build the solution in this order:

1. Define exactly what the candidate means.
2. Prove monotonicity.
3. Establish valid bounds, including a guaranteed feasible endpoint when required.
4. Implement and prove the decision procedure.
5. Apply the search template.

Common checks include:

• Greedy grouping: For nonnegative values, extend each contiguous group while its cost stays within the cap, then start another. This works for monotone costs such as sum or sum-plus-maximum, where shortening a group cannot increase its cost.
• Spacing and matching: After sorting positions, choose the earliest eligible position. It leaves maximal room for later choices. Mandatory selections must be built into the check; sorted injective matching must consume each position at most once.
• Resource budgets: Translate a candidate round count into remaining deficits. With baseline gain b, targeted extra gain e > 0, and requirement h, the needed targeted actions are max(0, ceil((h - rounds*b)/e)). Compare their total with available actions.
• Cardinality: Test whether k selections or assignments are possible. Ordered extremes, greedy matching, and sometimes a deque can make this efficient, but their correctness needs a separate argument.

Negative values require caution: greedy grouping and the implication that an at-most-k partition can be split into exactly k feasible groups may fail. Binary search may still apply, but feasibility can require dynamic programming.

3. Ranked selection through cumulative counts

To find the kth item in an implicit ordered collection, define count(x) as the number of items at most x. Search for the smallest x with count(x) >= k.

For a sorted distinct positive array, the number of missing positives through a[i] is a[i] - (i + 1). This count is monotone, so a boundary search locates where the kth missing value belongs.

For multiple arithmetic progressions, count each source's events up to a timestamp, cap counts for finite sources, and add them. If equal timestamps have a secondary ordering, first locate the timestamp, then resolve its tied events using that ordering.

4. Rotated sorted arrays

A rotated sorted array lacks one globally sorted interval, but usually one half around the midpoint remains sorted. Identify that half, check whether its value range contains the target, and discard the appropriate half.

Duplicates can make the sorted half ambiguous. Removing equal boundary values may be necessary, degrading the worst case to O(n).

Common mistakes

• Mixing closed and half-open interval update rules.
• Failing to make progress: use mid + 1 when excluding the midpoint, and an upper midpoint for last-true search.
• Treating a returned insertion position as an existing element without checking bounds.
• Searching a nonmonotone predicate or using an unproved greedy check.
• Choosing bounds that exclude the answer or lack the required feasible endpoint.
• Ignoring exact-count, mandatory-selection, tie-breaking, or one-use-only constraints.
• Using floating-point division for integer counts. For nonnegative integers, ceiling division is (x + d - 1) // d.

Complexity

Array lookup and boundary search take O(log n) time and O(1) auxiliary space.

Answer-space search takes O(T log R) time, where T is the cost of one feasibility check and R is the number of integer candidates. Sorting beforehand adds O(n log n).

For q independent sorted-array queries, searching costs O(q log n). A rank search with m counting sources typically costs O(m log R).

Space depends on the decision procedure: the search loop uses O(1), but sorting, deques, or dynamic programming may require additional storage.