Binary search and the bisect module¶

~20 min · prerequisite: Prefix sums and difference arrays

What you will be able to do¶

Find a position in a sorted list with the bisect module, and choose between bisect_left and bisect_right.
Search for the smallest or largest answer that satisfies a yes-or-no test.
Show that a binary search takes about log2 of the range size steps.

The idea¶

Binary search finds something in a sorted range by checking the middle and throwing away half of the range. Suppose you are looking for a word in a printed dictionary. You open near the middle, see whether your word comes before or after that page, and continue in one half. Each check halves the pages still in play.

The same idea works on a list. For a sorted list, the question "is the value at mid too small?" has a clear answer, and that answer tells you which half to keep. Python's standard library already has this search in the bisect module. The function bisect_left(values, x) returns the first index where x could be inserted while keeping the list sorted. bisect_right(values, x) returns the index after the last position that holds x. The two differ only when x is already in the list.

The second use of binary search is on an answer. Suppose a yes-or-no test ok(x) is monotone, which means it changes once: it is False for small values and True from some point on. Then the smallest x with ok(x) true can be found by the same halving.

Why are the steps few? Let d be the distance hi - lo between the two ends of the range. After one check, the new distance is at most d // 2. Starting from d, after s checks the distance is at most d / 2^s. The search ends when the distance reaches zero, which happens once 2^s is larger than d. So at most log2(d) + 1 checks are needed. For a range of a billion values, that is about 31 checks.

Worked example¶

The function below finds the smallest integer k with k * k >= n. The test k * k >= n is monotone, so binary search applies.

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


assert smallest_root_ceiling(50) == 8
assert smallest_root_ceiling(49) == 7

Line by line, this is what Python does for n = 50:

The answer lies in lo through hi, starting with 0 and 50. Both bounds are included.
The loop runs while the range has more than one value.
mid = (lo + hi) // 2 is the middle index, rounded down.
If mid * mid >= n, then mid is large enough, and the answer is mid or something smaller. So hi = mid keeps mid in the range.
Otherwise mid is too small, and the answer is at least mid + 1, so lo = mid + 1.
When lo equals hi, the loop stops and lo is the answer. For n = 50 it is 8, because 7 * 7 = 49 is too small and 8 * 8 = 64 is enough.

Try it¶

The first block checks bisect results on a small list. The second finds the largest square root with a search that rounds the middle up.

import bisect

values = [1, 2, 2, 2, 3]
left = bisect.bisect_left(values, 2)
right = bisect.bisect_right(values, 2)

assert left == 1
assert right == 4
assert right - left == 3
assert bisect.bisect_left(values, 10) == 5

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


for n in range(0, 2000):
    assert largest_root(n) ** 2 <= n < (largest_root(n) + 1) ** 2

Common mistakes¶

Mixing up bisect_left and bisect_right. With values = [1, 2, 2, 2, 3], the right index for 2 is 4, not 1:
```
import bisect

values = [1, 2, 2, 2, 3]
assert bisect.bisect_right(values, 2) == 1
```
```
AssertionError
```
Use bisect_left for the first position of a value, and subtract the two results to count copies.
Reading past the end of the list. When the search uses hi = len(values) as an index, the middle can point one place past the end:
```
values = [1, 2, 3]
print(values[len(values)])
```
```
IndexError: list index out of range
```
Check mid < len(values) before reading values[mid], or search on a range that ends at len(values) - 1.
Looping forever with while lo <= hi. If you use <= but still write hi = mid, the range can stop shrinking when lo equals hi. No error appears; the judge reports Time limit exceeded. Use while lo < hi with the update rules from the worked example.
Applying the search to a test that is not monotone. If ok(x) switches back and forth, the search can return a value that is not the smallest. No error appears, so test the rule on a few small inputs against a brute-force loop.

Practice¶

Easy: check that bisect.bisect_left([10, 20, 30], 25) is 2.
Easy: using bisect, count how many times 4 appears in [1, 4, 4, 4, 7]. The answer is 3.
Medium: write smallest_cube_root(n) that returns the smallest x >= 0 with x ** 3 >= n, using binary search. Check smallest_cube_root(1000) is 10 and smallest_cube_root(0) is 0.
Medium: write largest_root(n) as in the third runnable block, and check that largest_root(99) is 9.
Stretch: given a sorted list a and an integer q >= 0, count pairs i < j with a[j] - a[i] <= q. Use bisect_right for each i, and check the answer on [1, 3, 4, 8] with q = 3, which is 3.

Solution

```python import bisect

assert bisect.bisect_left([10, 20, 30], 25) == 2 ```

```python import bisect

values = [1, 4, 4, 4, 7] count = bisect.bisect_right(values, 4) - bisect.bisect_left(values, 4) assert count == 3 ```

```python def smallest_cube_root(n): lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 if mid ** 3 >= n: hi = mid else: lo = mid + 1 return lo

assert smallest_cube_root(1000) == 10 assert smallest_cube_root(0) == 0 ```

For n = 0, the range is 0 through 0, so the loop does not run and the answer is 0.

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

assert largest_root(99) == 9 ```

The middle is rounded up here. Without that, lo = mid could repeat forever when hi = lo + 1.

```python import bisect

def count_close_pairs(a, q): total = 0 for i in range(len(a)): reach = bisect.bisect_right(a, a[i] + q) total += reach - (i + 1) return total

assert count_close_pairs([1, 3, 4, 8], 3) == 3 ```

For each i, bisect_right gives the number of values at most a[i] + q. Subtracting i + 1 removes the values at or before i, so only later positions are counted.

Recap¶

bisect_left gives the first position for a value, and bisect_right gives the position after the last one.
Binary search on a monotone test finds the smallest or largest answer in about log2 of the range size steps.
Check the update rules when the range can shrink to two values, and make sure the middle index stays inside the list.