A sorted list answers questions quickly if you ask them the right way. To find where a timestamp belongs in a log of 200,000 entries, look at the middle entry. If it is earlier than the timestamp, the answer is in the right half; otherwise it is in the left half. Each look halves what is left, so 18 looks cover 200,000 entries.
The safest way to write it is as a search for a boundary, not for a value. Keep lo and hi so that the answer is always somewhere in [lo, hi], test the middle with a yes-or-no question, and move one end past the middle. When lo meets hi, that is the boundary. "The first index whose entry is at least t" has an answer even when t is not in the list, which is exactly what range counts need.
The same idea works when nothing is sorted at all, as long as the yes-or-no question is. "Can the queue be cleared in time at rate r?" is no for small rates and yes for every rate above some threshold. Search that threshold the same way: guess a rate, check it in one pass, and halve the range of rates. The answer space can be a billion wide; the search still takes about thirty checks.
Most bugs are off by one: a range that never shrinks, so the loop runs forever, or a boundary that is one step off. Decide what lo and hi mean, and make every update keep that meaning.
Recognise it
- The data is sorted, or a yes-or-no question about a candidate answer flips once from no to yes.
- The question asks for the first, last, smallest or largest something.
- A direct scan is too slow because it would repeat for many queries, or over a huge range of answers.
The shape of the code
// The first x in [lo, hi] for which ok(x) is true; hi itself must be a valid answer.
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (ok(mid)) hi = mid; // mid works: the answer is mid or to its left
else lo = mid + 1; // mid fails: the answer is to its right
}
return lo;