Card 05/ 08
Modified Binary Search Example: The Slowest Pump Rate That Empties Every Tank in Time
A faster pump never takes longer, so "empties every tank within eight hours" is false for slow rates and true from some rate on: binary search the rate.
Binary search can run over the possible answers to a problem rather than over an array, whenever checking a candidate answer gives a monotone yes or no. A crew must drain five flooded tanks holding 30, 11, 23, 4 and 20 thousand litres. Their pump can be set to any whole number of thousand litres an hour, it drains one tank at a time, and moving it to the next tank waits for the next full hour. The site must be dry within 8 hours, and a slower pump uses less fuel. What is the slowest rate that drains every tank in time?
What is the slowest rate?
15 thousand litres an hour, which takes 2 + 1 + 2 + 1 + 2 = 8 hours. At 14 the 30 and 23 still need 3 and 2 hours, and the total is 9.
Nothing here is sorted and no array is searched, which is why the cue is easy to miss. The candidates are the rates from 1 to 30, the size of the largest tank, since no faster rate can drain any tank in less than one hour. The predicate is "at this rate, the tanks are dry within 8 hours", and it is monotone: a faster pump never takes longer, so it is false for slow rates and true from some rate on. A tank of v at rate r takes v ÷ r hours rounded up, written ⌈v ÷ r⌉, because a part-hour still costs a whole one. The trace shows only the rates the search looks at, with … marking the ones it skips.
Inputtanks 30 11 23 4 20, at most 8 hours
Rate 15: 8 hours
- 1low
- …
- 8
- 9
- …
- 12
- 13
- 14
- 15mid
- …
- 30high
Rate 15 takes 8 hours, within the limit: high moves to 15
Rate 8: 13 hours
- 1low
- …
- 8mid
- 9
- …
- 12
- 13
- 14
- 15high
- …
- 30
Rate 8 takes 13 hours, over: low moves to 9
Rate 12: 9 hours
- 1
- …
- 8
- 9low
- …
- 12mid
- 13
- 14
- 15high
- …
- 30
Rate 12 takes 9 hours, over: low moves to 13
Rate 14: 9 hours
- 1
- …
- 8
- 9
- …
- 12
- 13low
- 14mid
- 15high
- …
- 30
Rate 14 takes 9 hours, over: low moves to 15
Done
- 1
- …
- 8
- 9
- …
- 12
- 13
- 14
- 15lowhigh
- …
- 30
low meets high at rate 15
ResultThe slowest rate that drains every tank within 8 hours is 15.
Tank by tank, the four tested rates come out like this.
| Rate | Hours per tank | Total | Within 8 |
|---|---|---|---|
| 8 | 4 2 3 1 3 | 13 | No |
| 12 | 3 1 2 1 2 | 9 | No |
| 14 | 3 1 2 1 2 | 9 | No |
| 15 | 2 1 2 1 2 | 8 | Yes |
The listing is the first-true template with the predicate swapped for the hours check. It writes the rounding up as -(-v // r), which stays in whole numbers.
tanks = [30, 11, 23, 4, 20]
limit = 8
def hours_at(rate: int) -> int:
return sum(-(-volume // rate) for volume in tanks)
low, high = 1, max(tanks)
while low < high:
mid = low + (high - low) // 2
hours = hours_at(mid)
within = hours <= limit
print(f"rate {mid}: {hours} hours, {'within' if within else 'over'} {limit}")
if within:
high = mid
else:
low = mid + 1
print(f"slowest rate: {low}")rate 15: 8 hours, within 8
rate 8: 13 hours, over 8
rate 12: 9 hours, over 8
rate 14: 9 hours, over 8
slowest rate: 15Checking every rate from 1 upwards would also find 15, after 15 checks; for tanks of a million litres the binary search needs about 20. Each check reads all n tanks, so the search is O(n log m) for a largest tank of m, which for 100,000 tanks of up to 10⁹ litres is about 3 × 10⁶ steps, well inside a one-second budget. Java writes the rounding up as Math.ceilDiv(v, r) from Java 18, or (v + r − 1) / r; TypeScript's Math.ceil(v / r) is exact for values this size.
← → move through sections and cards