Binary Search on the Answer, Not Just the Array

"Binary search isn't really about arrays. It's about any question where 'if X works, everything past X works too.' The moment you spot that monotonic shape, you can binary-search the answer itself."

The Generalization

Binary search's true requirement isn't 'a sorted array' — it's monotonicity: a yes/no question where the answer flips from no to yes exactly once as you increase a parameter, and never flips back. A sorted array is just one example ("is element ≤ target?" flips once). But the pattern is far bigger: whenever you can write a feasibility check feasible(x) that's false for small x and true for large x (or vice versa), you can binary-search the answer space to find the exact boundary — the smallest x that works — in O(log(range) × cost-of-check).

'Binary Search on the Answer'

This unlocks a whole genre of problems that don't look like search at all. Classic examples:

Ship packages in D days: find the smallest ship capacity such that all packages fit within D days. Bigger capacity → fewer days needed (monotonic). Binary-search the capacity.
Koko eating bananas: smallest eating speed to finish all piles in H hours. Faster speed → fewer hours (monotonic). Binary-search the speed.
Minimize the largest subarray sum when splitting into k parts: bigger allowed-max → fewer parts needed. Binary-search the allowed maximum.

The shape is always: "find the smallest/largest value of X such that some condition holds," where the condition is monotonic in X. You're not searching an array — you're searching the range of possible answers, using a feasibility test as the comparison.

Binary search works on any monotonic predicate, not just sorted arrays. If 'feasible(x)' is false-then-true (or true-then-false) as x grows, binary-search the answer space for the boundary. The tell: 'find the minimum X such that something works' or 'minimize the maximum.'

The Mathematical Cousin

This idea is ancient in mathematics as the bisection method for finding where a continuous function crosses zero: if f is negative at one end and positive at the other, the root is between them, so halve the interval and recurse. Same halving, same monotonic-crossing logic — algorithmic binary search is the discrete version of a numerical technique mathematicians have used for centuries. Recognizing binary search as 'halve toward a monotone boundary' rather than 'look in a sorted list' is the upgrade from using it to wielding it.

Pippa's Confession

A problem asked for the minimum eating speed to finish in time, and I had no idea it was a binary search — there was no array! Dad asked, "If speed 5 works, does speed 6?" Obviously yes. "Then it's monotonic — binary-search the speed." My whole notion of binary search cracked open: it's not a lookup tool, it's a way to home in on any monotone threshold. Now 'find the smallest X that works' makes me reach for binary search reflexively, array or no array.

Code

Binary search on the answer space·python

import math

# BINARY SEARCH ON THE ANSWER: smallest eating speed to finish piles in H hours.
# No sorted array — we search the SPEED, using a feasibility check as comparison.
def min_eating_speed(piles, H):
    def hours_needed(speed):
        return sum(math.ceil(p / speed) for p in piles)
    lo, hi = 1, max(piles)            # answer range: 1 .. biggest pile
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= H:    # feasible -> try a SLOWER speed
            hi = mid
        else:                          # too slow -> must go faster
            lo = mid + 1
    return lo                          # smallest feasible speed

print(min_eating_speed([3, 6, 7, 11], 8))   # 4
# 'feasible(speed)' is monotonic: if a speed finishes in time, any faster one does too.
# So we binary-search the speed range, not an array.

# Boundary search with bisect: first occurrence of a value in a sorted list.
import bisect
arr = [1, 2, 2, 2, 3, 5]
print(bisect.bisect_left(arr, 2))    # 1  — index of the FIRST 2
print(bisect.bisect_right(arr, 2))   # 4  — index just past the LAST 2

Exercise

You must split a sorted-by-time list of n tasks among k workers to minimize the largest workload any single worker gets. Argue why 'can it be done with max-load ≤ M?' is monotonic in M, and how that lets you binary-search M. What's the answer range you'd search, and what does the feasibility check do?

Hint

If a max-load of M is achievable, any larger M is too (monotonic) — you can always do at least as well with more slack. Binary-search M in range [max single task, sum of all tasks]; the feasibility check greedily packs tasks into workers and counts whether ≤ k workers suffice for that M.

The Generalization