Binary Search on Answer
SearchingHardVerify feasibility thresholds greedily using binary search.
Alt+Shift+A
Configuration Panel
Book Allocations Feasibility Visualizer
Time Complexity
O(N log(Sum - Max)) iterations
Space Complexity
O(1) auxiliary variables
Conceptual Overview
Binary Search on Answer finds the optimal (minimum or maximum) value that satisfies a feasibility function by running binary search on the range of all possible outcomes.
Algorithm Idea
Identify the bounds [low, high] of the solution space. For each mid, test if it is possible/feasible. Halve the bounds based on the result.
Stable Sorting
N/A
In-place Memory
N/A
Source: CP-Algorithms search & sorting reference