Why Binary Search on Answer Works: The Monotonicity Insight

Binary search on answer seems like magic: you're searching for an answer in a range, not in an array. How does this work?

The key is monotonic feasibility—if answer x works, then all answers in one direction also work. This creates an implicit sorted structure we can binary search on.

TL;DR

Binary search on answer works because:

1. Answer space has a range [min, max]
2. Feasibility is monotonic (if x works, x+1 works OR x-1 works)
3. We're finding the boundary between feasible and infeasible

Visual:

Answer space: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Feasibility:  [F, F, F, F, T, T, T, T, T, T]
                           ↑
                Find first T (minimum feasible)

The Core Insight: Monotonic Feasibility

What Is Monotonic Feasibility?

Definition: A feasibility function is_feasible(x) is monotonic if:

• For "minimize maximum": If is_feasible(x) = True, then is_feasible(x+1) = True
• For "maximize minimum": If is_feasible(x) = True, then is_feasible(x-1) = True

Why this matters: Monotonicity creates an implicit sorted structure:

[F, F, F, F, T, T, T, T, T, T]
            ↑
    Boundary between F and T

We can binary search for this boundary!

Example: Koko Eating Bananas

Problem: Find minimum eating speed to finish all bananas in h hours.

Answer space: [1, 2, 3, ..., max(piles)]

Feasibility: Can Koko finish with speed k?

Monotonicity check:

• If Koko can finish with speed 5, can she finish with speed 6? YES (faster is always ok)
• If Koko cannot finish with speed 4, can she finish with speed 3? NO (slower is worse)

Feasibility pattern:

Speed:        [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Can finish:   [F, F, F, T, T, T, T, T, T, T,  T]
                        ↑
              Find first T (minimum speed)

This is monotonic! We can binary search for the first True.

Mathematical Proof

Theorem

If feasibility is monotonic, binary search finds the optimal answer in O(log(max - min)) iterations.

Proof

Given:

• Answer space: [min_answer, max_answer]
• Monotonic feasibility function: is_feasible(x)

For "minimize maximum":

1. Invariant: At each step, the optimal answer is in [left, right]
2. Initial state: left = min_answer, right = max_answer
3. Binary search step:
   • Calculate mid = (left + right) // 2
   • If is_feasible(mid):
     • mid works, so optimal answer <= mid
     • All answers > mid also work (monotonicity)
     • Search left half: right = mid
   • Else:
     • mid doesn't work, so optimal answer > mid
     • All answers < mid also don't work (monotonicity)
     • Search right half: left = mid + 1
4. Termination: When left == right, that's the minimum feasible answer ∎

For "maximize minimum": Similar proof, but we search for the last True instead of first True.

Visual Proof: Koko Eating Bananas

Piles: [3, 6, 7, 11], h = 8

Answer space: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Check feasibility for each speed:
  Speed 1: 3+6+7+11 = 27 hours > 8 → F
  Speed 2: 2+3+4+6 = 15 hours > 8 → F
  Speed 3: 1+2+3+4 = 10 hours > 8 → F
  Speed 4: 1+2+2+3 = 8 hours <= 8 → T
  Speed 5: 1+2+2+3 = 8 hours <= 8 → T
  ...
  Speed 11: 1+1+1+1 = 4 hours <= 8 → T

Feasibility: [F, F, F, T, T, T, T, T, T, T, T]
                       ↑
              First T at index 3 (speed 4)

Binary search finds this boundary in log₂(11) ≈ 4 iterations

Why "Guess and Check" Works

The Algorithm

def binary_search_on_answer(min_val, max_val, is_feasible):
    left, right = min_val, max_val
    
    while left < right:
        mid = left + (right - left) // 2
        
        if is_feasible(mid):
            # mid works, try smaller (minimize)
            right = mid
        else:
            # mid doesn't work, need larger
            left = mid + 1
    
    return left

Why This Finds the Optimal Answer

Key insight: We're not searching for a specific value—we're searching for a boundary.

The boundary: The point where feasibility changes from False to True (or True to False).

Binary search finds boundaries efficiently because:

1. We can check which side of the boundary we're on (feasibility check)
2. Monotonicity tells us which direction to move
3. We halve the search space each iteration

When It Doesn't Work

Non-Monotonic Feasibility

Example (hypothetical):

Speed:        [1, 2, 3, 4, 5, 6, 7, 8]
Can finish:   [F, T, F, T, F, T, F, T]
               ↑  ↑  ↑  ↑
              No clear boundary!

Problem: Feasibility is not monotonic. Binary search would fail because:

• If speed 2 works, we can't assume speed 3 works
• We can't eliminate half the search space

Solution: Must use exhaustive search (O(n)) or different algorithm.

How to Verify Monotonicity

Ask these questions:

For "minimize maximum":

• If answer x works, does answer x+1 also work?
• If YES → Monotonic ✓
• If NO → Not monotonic ✗

For "maximize minimum":

• If answer x works, does answer x-1 also work?
• If YES → Monotonic ✓
• If NO → Not monotonic ✗

Examples

Example 1: Capacity To Ship Packages

Problem: Find minimum ship capacity to ship all packages in d days.

Monotonicity check:

• If capacity 15 works, does capacity 16 work? YES (larger capacity is always ok)
• Monotonic ✓

Feasibility pattern:

Capacity:   [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Can ship:   [F,  F,  F,  F,  F,  T,  T,  T,  T,  T,  T]
                                 ↑
                    Find first T (minimum capacity)

Example 2: Magnetic Force Between Two Balls

Problem: Maximize minimum distance between m balls.

Monotonicity check:

• If distance 5 works, does distance 4 work? YES (smaller distance is easier)
• Monotonic ✓

Feasibility pattern:

Distance:   [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Can place:  [T, T, T, T, T, F, F, F, F, F]
                         ↑
              Find last T (maximum distance)

Example 3: Split Array Largest Sum

Problem: Minimize the largest sum among m subarrays.

Monotonicity check:

• If max sum 18 works, does max sum 19 work? YES (larger max allows more flexibility)
• Monotonic ✓

Feasibility pattern:

Max sum:    [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
Can split:  [F, F, F, F,  F,  F,  F,  F,  F,  F,  F,  T,  T,  T]
                                                      ↑
                                          Find first T (minimum max)

Common Misconceptions

Misconception 1: "Binary search on answer is different from binary search"

False. It's the same algorithm, just applied to an implicit sorted structure (feasibility array) instead of an explicit sorted array.

Misconception 2: "I need to generate the feasibility array"

False. We never materialize the array. We just check feasibility for specific values (mid).

Misconception 3: "Feasibility check must be O(1)"

False. Feasibility check can be O(n) or even O(n²). Total complexity is O(log(max-min) × feasibility_cost).

FAQ

Q: How do I know if feasibility is monotonic?

A: Ask: "If answer x works, does x+1 work (or x-1)?" If yes, it's monotonic.

Q: What if I can't determine the answer range?

A: Look for natural bounds:

• Speed: [1, max_value]
• Capacity: [max_element, sum_all]
• Distance: [0, max_distance]

Q: Can feasibility be non-monotonic?

A: Yes, but then binary search on answer won't work. You'd need exhaustive search or a different approach.

Q: Why is this called "binary search on answer"?

A: Because we're searching the answer space (range of possible answers), not an array of elements.

Conclusion

Binary search on answer works because of monotonic feasibility—if answer x works, all answers in one direction also work.

Key principles:

• Answer space: Range of possible answers [min, max]
• Monotonic feasibility: If x works, x±1 works
• Boundary search: Find where feasibility changes from F to T

The algorithm:

1. Define answer range
2. Write feasibility function
3. Verify monotonicity
4. Binary search for boundary

When it works:

• Clear answer range
• Can check if candidate answer works
• Feasibility is monotonic

Understanding this principle helps you recognize binary search on answer opportunities and implement them correctly. For more details, see Binary Search on Answer Guide and Minimize Maximum vs Maximize Minimum.