Question Bank
Binary Search on the Answer
Difficulty: Medium
Cast feasibility problems as binary search over a monotone predicate. Drills cover min capacity, max chunk, and the standard template.
Binary Search on the Answer
Cast feasibility problems as binary search over a monotone predicate. Drills cover min capacity, max chunk, and the standard template.
1,159 views
33
You must ship weights over D days. Capacity cap is feasible if the ships can finish in D days. Write feasible(cap).
Examples
Example 1:
Input: weights = [1, 2, 3, 4, 5], D = 3, cap = 6
Output: True
Explanation: Greedy pack: [1, 2, 3] (sum 6), [4] (sum 4), [5] (sum 5). 3 ships, fits in D = 3 days.Example 2:
Input: weights = [1, 2, 3, 4, 5], D = 3, cap = 5
Output: False
Explanation: Greedy fills [1, 2] then [3] then [4] then [5] which is 4 ships, exceeding D = 3.What makes a problem suitable for binary search on the answer? Name the property and explain why it matters.
Build the wrapper that returns the minimum feasible cap using a feasibility predicate that greedily packs ships and returns whether the count is at most D, and a half-open binary search.
Examples
Example 1:
Input: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], D = 5
Output: 15
Explanation: Search [max(weights), sum(weights)] = [10, 55]. The smallest cap that finishes the shipment in 5 days is 15 (packs are [1..5], [6, 7], [8], [9], [10] or similar). The leftmost-true template returns 15.For a 'maximize the minimum' problem (e.g. place m boxes in n shelves to maximize the smallest gap), do you binary-search for the largest true or the smallest true, and what direction does the loop move?
What is the time complexity of binary search on the answer in terms of the answer range [lo, hi] and a per-feasibility cost T?