bisect and binary-search-on-the-answer

lesson 2-3 · ~13 min · 5/30

bisect and binary-search-on-the-answer

You will rarely re-type binary search for plain lookups, because Python ships it in the bisect module:

bisect.bisect_left(a, x): the first index where x could be inserted and keep a sorted. Equivalently, the index of the first element ≥ x.
bisect.bisect_right(a, x): the insertion point after any existing x values.

Two useful consequences:

bisect_right(a, x) - bisect_left(a, x) counts how many times x appears.
bisect_left answers "first element ≥ x" questions in O(log n), no loop required.

Code exercise · python

Run this. scores is sorted and 70 appears twice. Watch where bisect_left and bisect_right land around the 70s.

Quiz

For a sorted list a = [10, 20, 20, 30], what does bisect.bisect_left(a, 20) return?

Binary-search-on-the-answer

Here is the pattern that turns binary search from a lookup trick into a problem-solving weapon. It works when:

The answer is a number in a known range (a speed, a capacity, a size).
You can write a yes/no test like "is x big enough?"
The test is monotonic: once yes, always yes for bigger x.

Then you binary search the answer space instead of a list. Example: the integer square root of n is the largest x with x² ≤ n. The test x² ≤ n is monotonic (true, true, ..., true, false, false), so we can binary search x between 0 and n.

Code exercise · python

Run this. There is no list here at all. We binary search the range of possible answers 0..n and keep the last x that passed the x² ≤ n test.

Code exercise · python

Your turn, a real interview classic. A reader has `hours` hours and a list of chapter page counts. Reading at speed s, a chapter of p pages takes ceil(p / s) hours (you cannot split an hour across chapters). Write min_speed(piles, hours): the SMALLEST speed that finishes in time. Binary search speeds from 1 to max(piles).

Quiz

Which problem is a good fit for binary-search-on-the-answer?