ReviseAlgo Logo

Binary Search

Binary Search on Answer

Solve optimization problems by applying binary search to the answer value range using monotonic feasibility checks.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What is Binary Search on Answer?

Binary Search on Answer is an optimization technique. Instead of searching for an index in a sorted array, we binary search over the range of all possible answers (e.g., minimum speeds, maximum capacities, or lowest costs).

Why is it Important?

Many optimization problems (e.g., "minimize the maximum value") seem like they require complex dynamic programming or exhaustive search. However, if the feasibility of the answer is monotonic, we can formulate a decision check and use binary search to find the absolute boundary of feasibility in O(N log(range)) time.

Where is it Used?

  • Load Balancing: Distributing workloads among threads to minimize the maximum task execution time.
  • Factory Scheduling: Finding the minimum conveyor speed to process all inputs under a strict time limit.

    • 2. Mental Model: The Feasibility Slider

    Imagine a slider representing task execution capacity (e.g., conveyor speed).

  • If the slider is too low (speed = 1), the factory runs behind and tasks fail.
  • If the slider is set to maximum (speed = 10), the factory finishes way early, but at high cost.
  • Because the relationship is monotonic, there exists a single cutoff point (e.g., speed = 5). For any speed ≥ 5, we can successfully finish. For any speed < 5, we fail.

    • Instead of guessing speed, we slide the setting to the middle, check if the factory can complete tasks, and adjust our range accordingly.

    3. Core Concepts & Implementations

    Monotonicity & Feasibility Check

    Two conditions must be met to apply this pattern: 1. Monotonicity: If a capacity C works, any capacity > C must also work. If C fails, any capacity < C must also fail. 2. Fast Feasibility Check: We can write a helper function check(mid) (often using a greedy simulation) that returns true/false in O(N) time.

    Two Classic Interview Problems

    1. Koko Eating Bananas: Find the minimum eating speed K to eat all banana piles within H hours. 2. Capacity to Ship Packages: Find the minimum ship capacity to carry all packages within D days.

    4. Visual Trace: Shipping Packages [3, 2, 2, 4, 1] in 3 Days

  • lo = max(weights) = 4 (must be able to carry the heaviest package)
  • hi = sum(weights) = 12 (carry everything in one day)

    • 5. Real-World Applications

  • CPU Frequency Scaling: Dynamically adjusting CPU frequency to process a batch of sensor inputs in under X milliseconds while minimizing power.
  • Bandwidth throttling: Finding the minimum streaming bit-rate required to play video frames without buffering under network jitter.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Look for problems with optimization prompts:
  • "Find the minimum maximum value..." or "Find the maximum minimum value..."
  • "Split the array into M subarrays such that the maximum subarray sum is minimized." (Split Array Largest Sum -> equivalent to shipping packages!).

    • Common Mistakes

    Warning: 1. Incorrect lo Range Boundary: Initializing lo = 1 or lo = 0 in package shipping instead of max(weights). If capacity is smaller than max(weights), we can never pack the heaviest item, leading to infinite loops or incorrect evaluations.
    > 2. Non-Monotonic Conditions: Trying to apply this pattern when the feasibility function is not monotonic (e.g. speed X works, but speed X+1 fails due to task resonance).

    7. Summary

  • Answer Range: Define the boundaries on the possible output value space.
  • Check Function: Create an O(N) simulation check returning true/false.
  • Termination: Use boundary binary search (lo < hi) to locate the exact cutoff point.

    • 8. Quiz

    Question 1: What is the benefit of Binary Search on Answer over standard search? Answer: It converts an optimization problem ("find the absolute best value") into a decision problem ("is value X possible?"). Decision checks are usually simple O(N) greedy passes, yielding an extremely efficient O(N log(range)) solution.
    Question 2: In Koko Eating Bananas, why is the maximum speed upper bound initialized to max(piles)? Answer: Because Koko can only eat from one pile per hour. Eating at a speed faster than the largest pile size still takes exactly 1 hour for that pile, so any speed greater than max(piles) is redundant.
    Question 3: How do you perform ceiling division of integers (a / b) in Java/C++ without floating-point conversion? Answer: Use the formula (a + b - 1) / b. For example, (11 + 3 - 1) / 3 = 13 / 3 = 4, which matches ceil(11.0 / 3.0) = 4.0.
    Question 4: What is the time complexity of the "Split Array Largest Sum" problem on an array of size N with elements up to value V? Answer: O(N log(Sum)), where Sum \approx N × V. The binary search takes log(Sum) steps, and each feasibility check runs in O(N) time.
    Question 5: If the check function returns true for mid and we want to maximize the answer, how do we update the range boundaries? Answer: If we want to maximize the answer and mid is feasible, then we should check if a larger value works. We set lo = mid (or lo = mid + 1 if using exclusive bounds), instead of hi = mid.