Binary Search and Boundary Finding

The promise that makes halving possible

Binary search needs a monotonic search space: once a condition changes from false to true, it never changes back, or values are sorted so comparison tells which side is impossible.

For exact search in an ascending array, maintain an inclusive range [lo, hi] that may still contain the target:

1. Compute mid = lo + (hi - lo) // 2.
2. If the middle value is the target, return it.
3. If the middle value is too small, discard lo..mid.
4. If it is too large, discard mid..hi.

The range halves each time, so an array of one million values needs about 20 comparisons.

Loop invariants and templates

A loop invariant says what remains true before every iteration. In exact search, the invariant is: if the target exists, it is inside [lo, hi]. Every update must preserve it.

Two templates are common:

For the first position where a predicate is true:

• if valid(mid) is true, keep mid by setting hi = mid,
• otherwise discard mid by setting lo = mid + 1,
• when lo == hi, that boundary is the answer.

This same lower-bound pattern finds the first value at least a target, the first occurrence among duplicates, and the insertion position that preserves sorted order.

Binary search on the answer

Sometimes the input is not the search space. Suppose a problem asks for the smallest capacity that can ship packages within D days. For any capacity:

• capacities below some boundary are impossible,
• every capacity at or above the boundary is possible.

That feasibility predicate is monotonic, so binary-search capacity. This pattern appears in minimum speed, maximum minimum distance, workload allocation and cutting problems.

The design steps are:

1. State exactly what valid(x) means.
2. Prove that validity is monotonic.
3. Choose bounds that definitely contain the answer.
4. Use lower-bound search for the first valid answer or upper-bound search for the last valid answer.

Rotated arrays

In a sorted array rotated once, at least one half around the middle is still sorted. Identify that half, check whether the target lies inside its value range, and keep or discard it accordingly. Duplicates make the decision less informative; when nums[lo] == nums[mid] == nums[hi], shrinking the boundaries may be necessary.

Lower bound implementation

The program returns the first index whose value is at least the target. If every value is smaller, it returns the array length.

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


nums = [2, 4, 4, 4, 9, 13]
for target in (4, 5, 20):
    print(target, "->", lower_bound(nums, target))

4 -> 1
5 -> 4
20 -> 6

Failure modes

• Updating lo = mid in a lower-bound loop can stop progress when mid == lo; discard with mid + 1 when mid is known invalid.
• Mixing inclusive and half-open templates causes skipped candidates or out-of-range access.
• Binary-searching a non-monotonic predicate can return a plausible but meaningless boundary.
• If arithmetic bounds can be large, compute the middle as lo + (hi - lo) / 2 to avoid overflow in fixed-width languages.

Practice exact search in Binary Search, partitioning in Sort Three Colours, and divide-and-conquer counting in Count Inversions.