bisect and binary-search-on-the-answer

bisect and binary-search-on-the-answer

Plain binary search rarely gets re-typed for lookups, because Python ships it in the bisect module.

• bisect.bisect_left(a, x) gives the first index where x could be inserted while keeping a sorted, which is equivalently the index of the first element ≥ x.
• bisect.bisect_right(a, x) gives the insertion point after any existing copies of x.

Two consequences make these more useful than they first look.

• bisect_right(a, x) - bisect_left(a, x) counts how many times x appears, since the gap between the two insertion points is exactly the run of equal values.
• bisect_left answers first element ≥ x questions in O(log n) with no loop written by hand, which covers a surprising share of range queries.

Both take a sorted list, and neither checks that assumption. The third classic bug from lesson 2-2 applies here too.

Where the two insertion points land

The list is sorted and 70 appears twice, which is the case that separates left from right.

import bisect

scores = [55, 62, 70, 70, 81, 94]
print(bisect.bisect_left(scores, 70))
print(bisect.bisect_right(scores, 70))
print(bisect.bisect_left(scores, 75))
print(bisect.bisect_right(scores, 70) - bisect.bisect_left(scores, 70))

Output

2
4
4
2

bisect_left returned 2, the position of the first 70, so an inserted 70 would go before the existing ones. bisect_right returned 4, the position just past the last 70.

For a value that is absent, the two agree. bisect_left(scores, 75) returned 4, and bisect_right would return 4 as well, since there is no run of equal values to sit on either side of.

The subtraction on the last line gives 2, the number of 70s in the list, computed in two O(log n) searches without scanning anything.

The mnemonic is short. Left means before equals, right means after equals.

It returns 1.

bisect_left finds the first position where 20 could be inserted while keeping the list ordered, and that position is index 1, immediately before the existing 20s.

bisect_right(a, 20) would return 3 instead, just past them, and the difference of 2 is the count of 20s in the list.

The list is [10, 20, 20, 30], so a common wrong answer is 2, the index of the second 20. That value is where an inserted 20 would land under bisect_right semantics for a single element, which is not what left means.

Left means before equals, right means after equals, and every use of these functions comes back to that one distinction.

Binary-search-on-the-answer

Here is the pattern that turns binary search from a lookup trick into a problem-solving weapon. It applies when three conditions hold.

1. The answer is a number in a known range, such as a speed, a capacity, or a size.
2. You can write a yes or no test like is x big enough.
3. The test is monotonic, meaning that once the answer is yes it stays yes for every bigger x.

That third condition is what does the work. Monotonicity means the test results form a sorted pattern of no, no, no, yes, yes, yes, and a sorted pattern is exactly what binary search needs.

So you binary search the answer space rather than a list, and no list has to exist at all.

Take the integer square root of n, the largest x with x² ≤ n. The test x² ≤ n is monotonic in the other direction, true up to a point and false forever after, so x can be binary searched between 0 and n.

Integer square root

There is no list here, only a range of candidate answers.

def isqrt(n):
    lo, hi = 0, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

print(isqrt(36))
print(isqrt(37))
print(isqrt(99))

Output

6
6
9

The structure is the binary search from lesson 2-2, with nums[mid] == target replaced by a test on mid itself. That is the whole translation.

A passing mid moves lo up to look for something bigger, and a failing mid moves hi down. Since this hunts the largest passing value, the answer is hi when the loop ends, because hi holds the last value that passed.

isqrt(36) and isqrt(37) both return 6, which is correct for an integer square root. 6² = 36 ≤ 37 while 7² = 49 is too large, so 6 is the largest passer in both cases.

The cost is about log₂(n) tests rather than the n of counting upward, so isqrt on a trillion takes about 40 steps.

The smallest workable speed

A reader has a number of hours and a list of chapter page counts, and reading at speed s takes ceil(p / s) hours per chapter since an hour cannot be split across chapters.

import math

def min_speed(piles, hours):
    def can_finish(speed):
        return sum(math.ceil(p / speed) for p in piles) <= hours

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_speed([3, 6, 7, 11], 8))
print(min_speed([30, 11, 23, 4, 20], 5))

Output

4
30

can_finish is the yes-or-no test, one line summing the per-chapter hours and comparing against the budget. It is monotonic because a faster speed can never take more hours.

The bounds are worth justifying. Speed 1 is the slowest sensible value, and max(piles) is the fastest useful one, since any greater speed still spends one hour on the biggest chapter.

This variant hunts the smallest passing value, which changes two lines. A passing mid is kept alive with hi = mid rather than discarded, and the loop condition becomes while lo < hi so the range cannot collapse onto a checked-and-kept value forever.

When the loop ends lo and hi are equal, and that shared value is the answer. Compare isqrt, which hunted the largest passer and therefore returned hi after a lo <= hi loop.

The second case returns 30, the largest pile, which is the honest answer when the budget of 5 hours equals the number of chapters. One hour per chapter leaves no room to be slower.

The fit is finding the smallest ship capacity that ships all packages within d days.

All three conditions hold. Capacity is a number in a known range, from the largest single package up to the sum of all of them. Can we ship within d days at capacity c is a yes-or-no test. And a bigger capacity never hurts, so the test is monotonic.

That monotonicity is what makes the answer space searchable, since the results run no, no, no, yes, yes, and binary search halves that pattern like any sorted list.

Contrast finding the longest word in a list. There is no numeric answer space with a monotonic test over it, so binary search has nothing to shrink and a single O(n) pass is already optimal.

The tell is worth remembering. When a problem asks for the minimum or maximum value that still works, and a checker for a given value is easy to write, this pattern is usually the intended solution.