Algorithms - binary search

Binary search is not a sorted-array search algorithm. It’s an algorithm for finding the boundary in a monotone predicate — and most of its real uses are not on arrays at all.

The mental reframing

Stop thinking “find element in sorted array.” Start thinking: “I have a predicate p(x) that is false for small x and true for large x (or vice versa). Find the boundary.”

Examples that don’t look like binary search until you reframe:

• Koko eating bananas. Predicate: “can finish all piles in h hours at speed k?” Monotone in k. Search over [1, max(piles)].
• Capacity to ship within D days. Predicate: “can pack into D groups with max sum cap?” Monotone in cap.
• Median of two sorted arrays. Search the partition point in the smaller array; the predicate is “is the partition correct?”
• Allocating books / split array largest sum. Same shape — minimize the max chunk subject to a count constraint.

The template that doesn’t bug

Pick one and use it everywhere. The “find leftmost true” template:

lo, hi = lower_bound, upper_bound + 1   # half-open
while lo < hi:
    mid = (lo + hi) // 2
    if predicate(mid):
        hi = mid
    else:
        lo = mid + 1
return lo  # smallest x where predicate is true

Half-open intervals + lo < hi + lo = mid+1 / hi = mid is the combination that doesn’t infinite-loop on adjacent indices. Most binary-search bugs are people improvising the boundary conditions per problem.

On a sorted 2D matrix

If rows and columns are both sorted: walk from top-right (or bottom-left). Each step rules out a row or a column. O(m + n). Don’t reach for binary search here — the linear walk is cleaner and the same complexity class.

If the matrix is row-major sorted (each row strictly greater than the previous), treat as a 1D array of length m·n and binary-search once.

Where binary search does NOT apply

The predicate has to be monotone. If p(x) is true for some isolated x and false elsewhere, you don’t have binary search — you have linear scan or a different structure.