Binary Search on Answer

Opening scenario

Capacity To Ship Packages Within D Days (LC 1011). Packages with weights weights must ship in order; pick the minimum ship capacity so all packages ship within days days (each day's loaded weight ≤ capacity). weights=[1,2,3,4,5,6,7,8,9,10], days=5 → 15. Same family: Maximum Average Subarray II (LC 644) — return the largest average of any contiguous subarray whose length is at least k.

For shipping, assume a non-empty list of positive package weights, at least one allowed day, and indivisible packages loaded in the given order. For the average problem, assume a non-empty numeric array and 1 <= k <= len(nums). Start by testing one proposed capacity or average rather than trying to choose the optimum immediately. LC numbers identify LeetCode problems.

Question progression

Q1 — The array isn't sorted by the thing you want. Why think "binary search" at all?

Question: You want a minimum capacity. The weights aren't sorted by anything useful, and capacity isn't an element of the…