Binary and Monotonic Search

Search a boundary, not necessarily an input value

A sorted array's predicate a[i]≥target has that form. So does “this capacity completes the fixed workload within D days” if increasing capacity cannot hurt under the specified rules. An arbitrary boolean condition that alternates true and false does not.

Exact search uses a closed candidate interval

Start [left,right]=[0,n−1]. If a target exists, some eligible occurrence remains inside that closed interval. Equality may return immediately when any occurrence suffices. A smaller middle value excludes every index through middle; a larger value excludes every index from middle onward.

left, right = 0, len(nums) - 1
while left <= right:
    middle = left + (right - left) // 2
    if nums[middle] == target:
        return middle
    if nums[middle] < target:
        left = middle + 1
    else:
        right = middle - 1
return -1

The empty array starts with right=−1 and does not enter the loop. The returned −1 is an index sentinel, not an array access. Returning at equality is insufficient if the question asks for the first or last equal element.

First true uses a half-open interval

This lower-bound variant uses [left,right), initially [0,n). Positions before left are known too small; positions from right onward are known large enough. The answer may equal n, meaning insertion after the entire array. Never index a[n].

left, right = 0, len(nums)
while left < right:
    middle = left + (right - left) // 2
    if nums[middle] >= target:
        right = middle
    else:
        left = middle + 1
return left

right=middle keeps a successful middle as the possible boundary. Under left<right, middle is strictly below right, so that update still shrinks the interval. By contrast, left=middle can fail to progress when two endpoints are adjacent.

A closed-interval first-true variant saves each successful candidate before discarding it from the remaining search. Initialize the answer to one past the upper bound. All-false returns that sentinel; all-true returns the lower bound. This implementation and the half-open form locate the same boundary under their respective interval contracts.

def first_true(left, right, condition):
    answer = right + 1
    while left <= right:
        middle = left + (right - left) // 2
        if condition(middle):
            answer = middle
            right = middle - 1
        else:
            left = middle + 1
    return answer

For a last-true search with a true-to-false predicate, save a successful candidate and move left to middle+1; on false, move right to middle−1. The no-answer sentinel is one below the initial lower bound. Do not reverse the first-true updates without also changing the predicate and sentinel.

First equal is lower_bound followed by an in-bounds equality check. Upper bound changes the predicate to a[i]>target; upper−lower counts equal values. The last value ≤target is upper_bound−1, with −1 meaning none.

Search feasible answers

The answer may be absent from the input. For shipping indivisible positive loads in their existing order within D days, any capacity below max(loads) is impossible. sum(loads) is feasible for D≥1. A greedy feasibility pass fills each day until the next load would exceed capacity, then starts another day.

Increasing capacity cannot require more days under this model. Binary search can therefore find the least feasible integer capacity. The proof depends on ordered, unsplit loads and a specified daily rule; adding unrelated constraints may change the predicate.

For positive integer workloads and a speed v, a time check may sum ceil(workload/v). Larger v cannot increase that sum. Integer (workload+v−1)//v avoids floating rounding under safe arithmetic. If the time budget is smaller than the number of nonempty workloads when each requires a distinct unit of time, no finite speed works under that model.

Find bounds that contain the boundary and a feasible upper endpoint when needed. Exponential expansion can discover a bound only if eventual feasibility and overflow handling are established. A real-valued search also needs a tolerance or iteration rule; integer adjacent-endpoint termination is not interchangeable.

Order must survive the transformation

A rectangular matrix can be flattened by row = middle // columns and column = middle % columns only when its row-major sequence is globally sorted. Sorting each row individually is insufficient if the next row begins below the previous row's end. Handle empty dimensions before division/indexing.

A rotated sorted array has an ordered side that a comparison can identify when values are distinct. Test whether target lies within that ordered side's value bounds, then keep or discard it. Duplicates can hide which side is ordered; ambiguous equal boundaries can force linear worst-case work.

Time-based retrieval sorts versions by timestamp per key, then finds the last timestamp not exceeding the query. Median partition search across two sorted arrays is another transformed boundary: the left partition's maxima must not exceed the right partition's minima. Its partition sizes and edge sentinels need a separate proof, not the ordinary exact-search loop.

Interval updates must make progress

Inclusive [left,right] uses left≤right and typically ±1 updates. Half-open [left,right) uses left<right and may retain middle as right. “Always move both sides by one” and “never use right=middle” are both misleading rules without a convention.

For nonnegative indices in fixed-width arithmetic, left+(right−left)//2 avoids overflowing the sum left+right when the difference is representable. Arbitrary signed answer domains may need a safer midpoint policy. Python's arbitrary-precision integers do not have that fixed-width overflow.

The predicate must be consistent across probes. A noisy measurement or changing external state does not automatically produce a valid monotone boundary, even if its average trend looks monotone.

Test boundaries before trusting logarithmic time

Test empty and singleton domains; all false; all true; answer at either end; duplicates; no exact match; a feasible value between input values; and predicates at the proposed limits. Check both the returned position and whether it is a real match or merely an insertion point.

Write the monotone sentence, interval invariant and strictly decreasing interval width. These three statements are more reusable than memorizing one loop. Two-pointer elimination → also discards candidates using order, but normally traverses them instead of halving the interval.

Sources and connected topics

Python lower/upper insertion boundaries ↗

Choosing an algorithm → connects constraints to proof obligations.