Binary Search on the Answer

Terminology

Term	Definition
Binary search on the answer	Instead of searching for an element in an array, binary search over the range of possible answer values. For each candidate answer, check feasibility with a predicate function.
Monotonic predicate	A boolean function $f(x)$ over the answer space that transitions from FALSE to TRUE (or TRUE to FALSE) exactly once. Binary search finds this transition point.
Feasibility check	A function that, given a candidate answer, determines whether it satisfies the problem constraints. Must run in polynomial time (typically $O(n)$).
Answer space	The range $[\text{lo}, \text{hi}]$ of possible answer values. The lower bound is the smallest feasible answer, the upper bound is the largest.
Minimize the maximum	A problem pattern: find the smallest value $x$ such that some constraint is satisfiable. The predicate is "can we achieve this with $x$?"
Maximize the minimum	The dual pattern: find the largest value $x$ such that some constraint holds. The predicate flips direction.
Greedy feasibility	Most feasibility checks use a greedy scan: given a candidate answer, greedily assign elements and check if the constraint is met.

What & Why

Classic binary search finds a target in a sorted array. Binary search on the answer is a more powerful idea: instead of searching in the input, you search over the space of possible answers.

The pattern works when:

1. The answer lies in a bounded range [\text{lo}, \text{hi}]
2. There exists a monotonic predicate: if answer x is feasible, then all answers \geq x (or \leq x) are also feasible
3. You can check feasibility for a given candidate in O(n) or similar

This turns optimization problems ("find the minimum speed," "find the maximum capacity") into decision problems ("is speed x fast enough?"), which are often much easier to solve.

Classic examples include:

• Koko eating bananas: minimize eating speed such that all bananas are eaten within H hours
• Split array largest sum: minimize the largest subarray sum when splitting into K parts
• Capacity to ship packages: minimize ship capacity to deliver all packages within D days

How It Works

The Template

1. Define the answer space: \text{lo} = minimum possible answer, \text{hi} = maximum possible answer
2. Binary search: pick \text{mid}, check if \text{mid} is feasible
3. If feasible, try a smaller (or larger) answer. If not, try the other direction
4. Return the boundary value

Koko Eating Bananas

Koko has n piles of bananas and H hours. She eats at speed K bananas/hour (one pile at a time, rounding up). Find the minimum K such that she finishes in H hours.

The feasibility check: for a given speed K, compute total hours = \sum \lceil \text{pile}_i / K \rceil. If total \leq H, the speed is feasible.

Complexity Analysis

Problem	Brute Force	Binary Search on Answer	Space
Koko eating bananas	$O(n \cdot \max)$	$O(n \log \max)$	$O(1)$
Split array largest sum	$O(n^K)$ DP	$O(n \log S)$ where $S$ = total sum	$O(1)$
Ship packages in D days	$O(n \cdot S)$	$O(n \log S)$	$O(1)$

The binary search runs $O(\log R)$ iterations where $R$ is the answer range. Each iteration runs the feasibility check in $O(n)$:

Implementation

Koko Eating Bananas

ALGORITHM MinEatingSpeed(piles, n, H)
  INPUT: array piles of size n, hours limit H
  OUTPUT: minimum eating speed K

  lo = 1
  hi = MAX(piles)

  WHILE lo < hi DO
    mid = lo + (hi - lo) / 2

    IF CanFinish(piles, n, mid, H) THEN
      hi = mid          // try slower
    ELSE
      lo = mid + 1      // need faster
    END IF
  END WHILE

  RETURN lo
END

ALGORITHM CanFinish(piles, n, speed, H)
  hours = 0
  FOR i = 0 TO n - 1 DO
    hours = hours + CEIL(piles[i] / speed)
  END FOR
  RETURN hours <= H
END

Split Array Largest Sum

ALGORITHM SplitArrayLargestSum(A, n, K)
  INPUT: array A of size n, split into K subarrays
  OUTPUT: minimized largest subarray sum

  lo = MAX(A)        // at least the largest element
  hi = SUM(A)        // at most the total sum

  WHILE lo < hi DO
    mid = lo + (hi - lo) / 2

    IF CanSplit(A, n, K, mid) THEN
      hi = mid
    ELSE
      lo = mid + 1
    END IF
  END WHILE

  RETURN lo
END

ALGORITHM CanSplit(A, n, K, maxSum)
  splits = 1
  currentSum = 0

  FOR i = 0 TO n - 1 DO
    IF currentSum + A[i] > maxSum THEN
      splits = splits + 1
      currentSum = A[i]
      IF splits > K THEN RETURN FALSE
    ELSE
      currentSum = currentSum + A[i]
    END IF
  END FOR

  RETURN TRUE
END

Capacity to Ship Packages

ALGORITHM ShipWithinDays(weights, n, D)
  INPUT: array weights of size n, days limit D
  OUTPUT: minimum ship capacity

  lo = MAX(weights)
  hi = SUM(weights)

  WHILE lo < hi DO
    mid = lo + (hi - lo) / 2

    IF CanShip(weights, n, D, mid) THEN
      hi = mid
    ELSE
      lo = mid + 1
    END IF
  END WHILE

  RETURN lo
END

ALGORITHM CanShip(weights, n, D, capacity)
  days = 1
  currentLoad = 0

  FOR i = 0 TO n - 1 DO
    IF currentLoad + weights[i] > capacity THEN
      days = days + 1
      currentLoad = weights[i]
      IF days > D THEN RETURN FALSE
    ELSE
      currentLoad = currentLoad + weights[i]
    END IF
  END FOR

  RETURN TRUE
END

Real-World Applications

• Load balancing: distributing tasks across servers to minimize the maximum load per server is a "split array largest sum" problem.
• Logistics optimization: determining the minimum truck capacity to deliver all packages within a deadline maps directly to "capacity to ship."
• Manufacturing: finding the minimum production rate to meet demand within a time window uses the same binary search on rate pattern.
• Network bandwidth allocation: minimizing the maximum link utilization when routing flows across a network uses binary search on the answer.
• Competitive programming: "binary search the answer" is one of the most common techniques in contests, applicable whenever the feasibility predicate is monotonic.

Key Takeaways

• Binary search on the answer converts optimization problems into decision problems: "can we achieve answer $x$?" is often much easier than "what is the optimal answer?"
• The technique requires a monotonic predicate: if $x$ is feasible, then all values on one side of $x$ are also feasible
• The answer space bounds are critical: $\text{lo}$ is the smallest possible answer, $\text{hi}$ is the largest. For "minimize the maximum," $\text{lo} = \max(\text{elements})$ and $\text{hi} = \text{sum}(\text{elements})$
• The feasibility check is usually a greedy $O(n)$ scan, making the total complexity $O(n \log R)$ where $R$ is the answer range
• Recognize the pattern: "minimize the maximum" or "maximize the minimum" with a constraint on the number of splits/days/groups