Binary Search

Binary search finds a boundary in an ordered candidate space. The key is a monotonic predicate: once a candidate is classified as “after,” every later candidate must also be “after.”

1. The Transition-Point Recipe

Reframe the search space as two monotonic regions:

before  before  before  before | after  after  after
                                ^
                          transition point

Define is_before(x) so every “before” candidate comes before every “after” candidate. The values themselves do not need to be booleans; only this classification must be monotonic.

def first_after(first, last, is_before):
    if first > last or not is_before(first):
        return first
    if is_before(last):
        return last + 1
    left, right = first, last
    while right - left > 1:
        mid = left + (right - left) // 2
        if is_before(mid):
            left = mid
        else:
            right = mid
    return right

The loop never changes:

• left remains known “before,” and right remains known “after.”
• mid is strictly between them, so every iteration makes progress.
• When they are adjacent, left and right identify the transition.

The function searches inclusive integer bounds [first,last] and returns the first after index, or last+1 if all candidates are before. Empty input returns first. For a lower bound, call first_after(0, len(nums)-1, lambda i: nums[i] < target); check the returned index is in bounds before checking equality. For an upper bound, use nums[i] <= target instead. Subtract lower from upper to count occurrences.

2. Translate the Task into a Predicate

For the rotated minimum, values before the pivot exceed the last value and values from the pivot onward do not. Duplicates can destroy that separation: [1,0,1] is a counterexample. For capacity search, proving that required group count never increases with capacity is part of the solution, not an assumption supplied by the binary-search loop.

3. Reusable Idea: Grid Flattening

If an R x C grid is sorted in complete row-major order, imagine it as one virtual sorted array of length R * C. Do not allocate that array; translate indices only when reading a cell:

• Grid to virtual index: i = r * C + c.
• Virtual index to grid: r = i // C, c = i % C.

This produces an $O(\log(RC))$ search with $O(1)$ extra space. It is valid only when each row is sorted and the last value of one row is smaller than the first value of the next row.

4. Reusable Idea: Exponential Search and Guess-and-Check

When a search range has no known upper bound, probe 1, 2, 4, 8, ... until the predicate changes. The last two probes bracket the transition; then apply the normal recipe inside that interval.

left, right = 0, 1
while is_before(right):
    left = right
    right *= 2

# The transition is now in (left, right].
answer = first_after(left, right, is_before)

This pairs naturally with guess-and-check:

1. Guess a candidate answer.
2. Check whether it is too small, too large, feasible, or infeasible.
3. Prove those answers form one monotonic transition.
4. Binary search for the first or last candidate that satisfies the constraint.

Use this when checking one candidate is much easier than constructing the optimum directly. If the answer bounds are unknown, exponential search can discover them first.

5. Complexity and Key Takeaways

A range of N candidates needs $O(\log(N+1))$ predicate evaluations. If a feasibility check scans n items, total time is $O(n\log(N+1))$, not just logarithmic. Auxiliary space includes whatever the predicate allocates.

• State the first-after return convention and check the last+1 sentinel before indexing.
• Empty, all-before, all-after, one-item and duplicate-heavy inputs must follow the same contract.
• A globally sorted flattened grid works; a grid with only each row sorted does not give one global transition.
• Repeated doubling needs a guaranteed finite transition or a known limit. Handle index overflow and out-of-range probes; otherwise bound discovery may never stop.

For splitting a nonnegative array into at most k groups while minimizing the maximum group sum, a guessed capacity can be checked by greedily filling each group. More capacity never requires more groups, so binary search can find the smallest feasible capacity. Prove that monotonicity for each new problem; an arbitrary local trend or a rotated array with ambiguous duplicates may require different handling.

Continue to Two Pointers when candidates can be eliminated one at a time, Sorting to establish order, and Dynamic Programming when a feasibility check itself has overlapping subproblems.