Binary search on the answer

Say you want to read “War and Peace” in a month: a few chapters a day, in order, never splitting a chapter. How many words will you have to read on the heaviest day if the chapters are spread as well as possible? Trying every way to lay out 361 chapters of the Russian original over 30 days is hopeless. But checking a particular limit, “will 15 thousand words a day be enough?”, takes one pass over the chapters. And if so, the answer can be found by halving. Move the number of days.

In 30 days: at most 15,802 words a day, about eighty minutes of reading. Perfectly even would be 15,088, but chapters cannot be cut. Over a year the answer is 3476: the length of the longest chapter, and no number of days can get below it. And for any k the search makes about nineteen checks.

The idea

Instead of asking “what is the smallest limit?” we ask “is the limit L enough?”. The answer to that is monotone: if L is enough, any larger limit is enough too. So on the axis of limits there is a boundary, “not enough” on the left and “enough” on the right, and an ordinary binary search finds it, searching not an array but the answers themselves.

Here is that boundary on a chart. The larger the daily limit, the fewer days are needed: the function goes down in steps. We look for the first point where it has dropped to k days or below. Each probe is a check of one L; green ones are enough, red ones are not, and the search range halves every time.

The technique needs two things. A monotone check: “fits” for one value implies “fits” for all larger ones (or for all smaller ones). And a cheap check: answering “is L enough” is much easier than finding the best L. Here the check is greedy: put the next chapter into the current day while it fits, otherwise start a new day. Greed is right here: if some plan fits into k days, so does the greedy one, since by any given moment it has filled each day at least as much as any other plan.

Code

The search range runs from the longest chapter (it cannot be less) to the sum of all chapters (the whole novel in a day). Until the range shrinks to a point, check the middle: if it is enough, the right end moves to the middle; if not, the left end moves past it.

The number of checks is log₂ of the width of the range: from 3476 to 452,626 words is about 449 thousand values, 19 halvings. Each check is a pass over 361 chapters. Trying the limits one after another from the longest chapter up would take more than twelve thousand checks for a month.

The first yes and the last yes

Problems come in two kinds, and they differ in one line.

• The smallest that fits: “what is the smallest limit that lets us finish in time”. The check says yes to the right of the boundary. The middle is rounded down; on yes the right end moves to the middle, on no the left end moves to the middle plus one.
• The largest that fits: “how far apart can the stations be placed”. The check says yes to the left of the boundary. The middle is rounded up, (lo + hi + 1) / 2, otherwise on two neighbouring numbers the search marks time forever. This is the article's second problem.

If the answer is real, a speed, a time, a length, then instead of “until the range shrinks” a fixed number of steps is made: a hundred halvings narrow the range 2¹⁰⁰ times, enough for any precision a double can hold. This is how the bisection method for roots of equations works.

What it costs

O(log D) checks, where D is the width of the range of possible answers, times the cost of one check. Here a check is O(n), and altogether it is O(n log S), where S is the sum of the chapter lengths. The logarithm of the range width grows slowly: even if the answer can be any number up to 10¹⁸, sixty checks will do.

The main work is noticing that the problem can be turned around. The signs: the statement says “minimise the largest” or “maximise the smallest”, the answer is a number from a wide range, and checking a particular number is greedy or simple. If the check is not monotone, though, so that increasing the parameter flips “fits” to “does not fit” and back, binary search will give a wrong answer without any warning.

Problems

The first is the reading plan from the scene for several deadlines at once. In the second the largest value that fits is sought, and the middle has to be rounded up; the test is the 177 crossroads of a route across the whole centre of Almaty.