When binary searching for a minimum charging rate, what does the range hold and what does a midpoint test?

## The shape of the question Some optimization questions hand you a sequence and ask for a **threshold** rather than for something *in* the sequence. "What is the smallest per-unit rate, capacity, budget or speed that still lets this fixed workload finish inside a fixed limit?" The sequence itself is fixed, its order is fixed, and the thing you are solving for never appears in it. That is the signal for binary search on the answer. Make it concrete. A bus depot has one charging bay. Buses are charged one after another in a fixed order. Bus `i` needs `need[i]` kilowatt-hours. Depot policy says a bus occupies the bay for a whole number of hours, so at a charging rate of `r` kilowatts, bus `i` ties up the bay for `ceil(need[i] / r)` hours. There are `H` hours until 6am. Find the smallest integer rate `r` that gets every bus charged in time. ## Why not search the input Ordinary binary search needs a sorted array and compares the target against `a[mid]`. Here there is no such array. Sorting the buses by need changes nothing — the total hours at a given rate is the same sum whatever order you charge in — and no bus's need *is* the answer. Indices are the wrong universe entirely: the answer is a rate, and rates live on a number line of their own. What *is* usable is that the rate line has an order the problem respects. If 40 kilowatts gets everyone charged by 6am, so does 41; if 39 fails, so does every rate below it. So the rate line splits cleanly into a failing prefix and a succeeding suffix, and finding the boundary between them is exactly what binary search does — with the comparison against `a[mid]` replaced by a **feasibility check** that takes a candidate rate and returns a boolean. ## What the range actually contains The low end is 1 (a rate of 0 charges nothing). The high end is `max(need)`: at that rate the largest bus finishes within a single hour, and so does every other bus, which is the smallest number of hours the schedule can ever take. Raising the rate beyond `max(need)` cannot reduce the hour count further, because the whole-hour rounding already floors every bus at one hour. So the entire useful answer space is the integers from 1 to `max(need)`, and the number of iterations is about `log2(max(need))` — a property of the *values*, not of how many buses there are. ## Why the rounding matters If a bus's charging time were `need[i] / r` hours exactly, the total would be `sum(need) / r` and you could solve for `r` in one line of algebra — no search needed. The ceiling is what breaks the closed form: each bus wastes part of its final hour, and how much waste there is depends on `r` in a way you cannot invert. Almost every problem in this family has such a wrinkle — whole units, contiguity, an indivisible item — and it is precisely the wrinkle that makes searching the answer worth doing. ## The feasibility check ``` feasible(need, H, r): hours = 0 for i in 0..length(need)-1: hours = hours + ceil(need[i] / r) return hours <= H ``` One pass, no extra storage, returns a boolean. Binary search calls it about `log2(max(need))` times and never looks at the input any other way. That separation is the whole technique: a *search* over values, plus a *simulation* that scores one value. ## Recognizing it in an interview The tells are consistent. You are asked for a minimum or maximum **number** that is not an element of the input; a candidate number is easy to *verify* even though it is hard to *derive*; and pushing the number in one direction only ever makes verification easier. When all three hold, say out loud that the search space is the value range, name its endpoints, describe the check and its cost, and only then talk about the loop. Candidates who jump straight to loop mechanics usually end up binary-searching the wrong universe. ## The most common wrong turns Sorting the input first, on reflex, and then trying to binary search it. Reporting the complexity as `O(log n)` because the words "binary search" were said. Trying to invert the arithmetic and forgetting the rounding. And answering with *a* feasible rate rather than the smallest one — the search has to keep narrowing after the first yes, not stop at it.