Overview
Binary Search on the Answer applies when a problem asks for the minimum or maximum value satisfying a condition, and that condition is monotonic. A monotonic condition changes in only one direction as the candidate answer increases or decreases, allowing half of the search space to be eliminated at each step.
Core idea
Instead of calculating the optimal answer directly, choose a candidate value and test whether it is feasible. If the candidate is feasible, search for a better answer in the appropriate direction. If it is infeasible, eliminate that portion of the search space.
How it works
Determine the minimum and maximum possible answers.; Define a feasibility function that checks a candidate answer.; Verify that the feasibility result is monotonic.; Calculate the midpoint of the current answer range.; If the midpoint is feasible, move toward a potentially better answer.; If it is not feasible, discard the invalid half.
Key concepts
Monotonic feasibility; Candidate answer; Search boundaries; Minimum feasible value; Maximum feasible value; Optimization problems
Time complexity
operation: Binary search iterations; complexity: O(log R), where R is the size of the candidate range; operation: Total algorithm; complexity: O(T × log R), where T is the time required by one feasibility check
Space complexity
Depends on the feasibility-check implementation; the binary-search control logic generally uses O(1) auxiliary space.
Example
problem: Find the minimum capacity required for a container to ship packages within a specified number of days.; packageWeights: 3; 2; maximumDays: 3; candidate: 6; feasibility: A capacity of 6 can ship the packages in three days: [3, 2], [2, 4], [1, 4].; result: The candidate capacity is feasible, so the search can test smaller capacities.