Binary Search

The previous lesson ended with a sign-up log and a question: where in that log does day thirty start? Start by making the log. It holds a million timestamps from one month. Each one is the number of seconds since the month began, and they are sorted from the earliest to the latest.

import random

r = random.Random(2)
timestamps = sorted(r.randrange(30 * 86_400) for _ in range(1_000_000))
len(timestamps), timestamps[:3], timestamps[-1]

(1000000, [2, 2, 5], 2591999)

There are a million entries. The first ones are 2, 2 and 5 seconds, and the last is 2,591,999.

A day has 86,400 seconds, so day thirty starts at 29 * 86_400. The function first_at_or_after goes through the timestamps from the start, and returns the index of the first one at that time or later:

def first_at_or_after(values, t):
    for i, value in enumerate(values):
        if value >= t:
            return i
    return len(values)
first_at_or_after(timestamps, 29 * 86_400)

966504

It finds index 966,504, and when this was timed it took about 79 milliseconds.

What the order tells you

That function is a linear search: it checks the values one at a time, from the start, like the searches in the previous lesson. It checks every value in turn because it does not use anything about their order. But these values are sorted, and that gives you a lot of information.

See it on something small. Here are ten prices, sorted, from 23 up to 59. You are looking for 25. The middle price, at index 4, is 37:

prices = [23, 25, 28, 32, 37, 42, 48, 49, 56, 59]
prices[4]

37

Compare 25 with that middle price: 25 is smaller than 37. And because the list is sorted, every price from 37 onwards is bigger than 25 as well. So with one comparison, you know that half the list cannot contain 25, without checking any of it.

How few comparisons, then, can it take to find a value in a sorted list?

The idea is to keep track of the part of the list that could still contain the value. Call its first index lo, for low, and its last index hi, for high. At the start, lo is 0 and hi is 9.

The middle index, mid, is lo plus hi, floor divided by two: (0 + 9) // 2, which is 4. And prices[4] is 37.

Tracing each step

Here is that search as a loop, with a print of lo, mid, hi and the middle price on each iteration, the way you traced code when debugging, so you can see each step:

lo, hi = 0, len(prices) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    print(lo, mid, hi, prices[mid])
    if prices[mid] == 25:
        break
    elif prices[mid] < 25:
        lo = mid + 1
    else:
        hi = mid - 1

0 4 9 37
0 1 3 25

The first line is 0 4 9 37, and the second is 0 1 3 25.

A value that is not in the list

So what happens with a value that is not in the list, like 30? Here is the same loop, searching for 30, with lo, hi on the last line so you can see where they end up:

lo, hi = 0, len(prices) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    print(lo, mid, hi, prices[mid])
    if prices[mid] == 30:
        break
    elif prices[mid] < 30:
        lo = mid + 1
    else:
        hi = mid - 1
lo, hi

0 4 9 37
0 1 3 25
2 2 3 28
3 3 3 32
(3, 2)

The first step is the same: 30 is smaller than 37, so hi becomes 3. Then mid is 1, and 25 is smaller than 30, so this time lo moves up, to mid + 1, which is 2. Then mid is 2, and 28 is smaller too, so lo becomes 3. And then mid is 3, and 32 is bigger than 30, so hi becomes 2.

Now lo is 3 and hi is 2. Low has passed high, so the range is empty, which means 30 is not in the list. It took four comparisons to find that out, and each comparison ruled out about half of what was left.

That is binary searchKey termFinding a value in a sorted list by comparing it with the middle of the range, and keeping the half that can still hold it.. It finds a value in a sorted list by comparing it with the middle of the range, and keeping only the half that could still contain it.

Now write it as a function. binary_search takes the values and a target. It sets lo to 0 and hi to the last index. Then, while lo is less than or equal to hi, it computes mid.

• If the value at mid is the target, it returns mid.
• If the value at mid is smaller, the target can only be to the right, so lo becomes mid + 1.
• Otherwise, it can only be to the left, so hi becomes mid - 1.

And if the loop ends, lo has passed hi, so it returns -1, meaning not found.

It also counts its comparisons, the same way the functions in the previous lesson did, and returns the count with its answer:

def binary_search(values, target):
    lo = 0
    hi = len(values) - 1
    comparisons = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        comparisons += 1
        if values[mid] == target:
            return mid, comparisons
        elif values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons
binary_search(prices, 25)

(1, 2)

Searching prices for 25 gives index 1, after two comparisons.

Three more searches

Try three more: the last price, the first price, and a value that is not there.

[binary_search(prices, t) for t in (59, 23, 30)]

[(9, 4), (0, 3), (-1, 4)]

59, the last price, is found at index 9 after four comparisons. 23, the first price, takes three. And 30, which is not there, gives -1 after four, the same four steps you followed by hand.

So far

Binary search compares the target with the middle of the range, and keeps the half that can still contain it. It stops when it finds the target, or when the range is empty.

So how many comparisons does binary search need as the list grows? Each comparison halves the range. Take a list of 1,024 values. After one comparison, 512 are left, then 256, and so on, down to one. Count the halvings with a loop:

n = 1_024
halvings = 0
while n > 1:
    n = n // 2
    halvings += 1
halvings

10

There are ten.

Logarithms

The number of times you can halve n before you get to one has a name: it is the logarithm to the base two of n, written log₂ n. The math module calculates it with math.log2:

import math
[math.log2(n) for n in (2, 4, 8, 16, 1_024)]

[1.0, 2.0, 3.0, 4.0, 10.0]

log₂ of 2 is 1, of 4 is 2, of 8 is 3, of 16 is 4, and of 1,024 it is 10.

So for 1,024 values, binary search makes about ten comparisons, plus one for the last value that is left. Try every target, from -1 to 1,024, and take the most comparisons any of them needs:

numbers = list(range(1_024))
max(binary_search(numbers, t)[1] for t in range(-1, 1_025))

11

The most it ever makes is eleven.

A million values

Logarithmic time

So binary search is O(log n), which is called logarithmic timeKey termO(log n): the operations grow by one each time n doubles. Binary search on 1,000,000 values makes at most 20 comparisons.. And look at the difference it makes. Here is the most comparisons binary search needs for a thousand values:

thousand = list(range(1_000))
max(binary_search(thousand, t)[1] for t in range(-1, 1_001))

10

When the list got a thousand times bigger, from a thousand values to a million, linear search made a thousand times as many comparisons in the worst case, while binary search made only about ten more: twenty instead of ten.

Everything binary search does depends on the list being sorted. Here are the same ten prices in a different order, and you search for 25 again:

shuffled = [42, 23, 59, 28, 49, 25, 37, 56, 32, 48]
binary_search(shuffled, 25), 25 in shuffled

Sort once, search many times

Sorting takes time too, because sorted is O(n log n), which is more than one linear search. So if you only search once, a linear search on the list as it is will often be faster, and it is worth timing both on your own data.

But when you search many times, you only sort the one time, and every search after that is O(log n). Sorting the million timestamps took about 0.22 seconds when it was timed. After that, each binary search takes a fraction of a microsecond, where each scan took about 79 milliseconds. So three scans take longer than sorting once and searching three times.

You will not often write binary search yourself, because Python's standard library has it, in the bisect module. bisect_left takes a sorted list and a value, and returns the index where that value would go to keep the list sorted:

from bisect import bisect_left
bisect_left(prices, 25), bisect_left(prices, 30), bisect_left(prices, 100)

(1, 3, 10)

For 25, it gives 1, because 25 is at index 1. For 30, which is not there, it gives 3, because 30 would go between 28 and 32. And for 100, it gives 10, the end of the list.

Checking whether the value is there

So bisect_left does not tell you whether the value is there. To find out, you check that the index is inside the list, and that the value at that index is the one you searched for. That is what the function found does here:

def found(values, target):
    i = bisect_left(values, target)
    return i < len(values) and values[i] == target
found(prices, 25), found(prices, 30), found(prices, 100)

(True, False, False)

It gives True for 25, and False for 30 and for 100.

insort

The same module also has insort, which inserts a value at its sorted position, after any equal values, so the list stays sorted. Finding the position is O(log n), but moving the later items up makes the insert itself O(n). Here it inserts 30 into a copy of prices:

from bisect import insort
more = list(prices)
insort(more, 30)
more

[23, 25, 28, 30, 32, 37, 42, 48, 49, 56, 59]

insort(more, 30) puts 30 between 28 and 32.

On a million sorted numbers, bisect_left took about 0.2 microseconds when it was timed, while checking with in, which is a linear search, took about 6 milliseconds.

There are two mistakes people often make when they write binary search themselves.

Setting hi to mid

The first is setting hi to mid, instead of mid - 1, while the loop still runs as long as lo is less than or equal to hi. Here is that version, searching for 30. It uses a for loop with a limit of six steps instead of a while loop, so that the cell ends:

lo, hi = 0, len(prices) - 1
for step in range(6):
    if lo > hi:
        break
    mid = (lo + hi) // 2
    print(lo, mid, hi)
    if prices[mid] < 30:
        lo = mid + 1
    else:
        hi = mid

0 4 9
0 2 4
3 3 4
3 3 3
3 3 3
3 3 3

It goes 0 4 9, then 0 2 4, then 3 3 4. And then it prints 3 3 3, again and again.

When lo and hi are both 3, mid is 3 as well, and 32 is bigger than 30. So hi is set to mid, which is 3, and nothing changes. Without the limit, that loop would never end. It is the - 1 and the + 1 that make the range smaller every time.

Dividing with one slash

The second mistake is computing mid with one slash instead of two:

mid = (0 + 9) / 2
prices[mid]

TypeError: list indices must be integers or slices, not float

0 plus 9, divided by two, is 4.5, which is a float:

mid

4.5

A list index must be an integer, so prices[4.5] raises the TypeError. Floor division, (0 + 9) // 2, gives 4, which is an int.

Now go back to the log. bisect_left of the timestamps, with the start of day thirty, gives the same index the scan found:

i = bisect_left(timestamps, 29 * 86_400)
i, len(timestamps) - i, i == first_at_or_after(timestamps, 29 * 86_400)

(966504, 33496, True)

It gives 966,504, which means there are 33,496 entries on the last day. And bisect_left found it in about a fifth of a microsecond when it was timed, where the scan took about 79 milliseconds.

Databases use the same halving to find a row by its index, instead of reading the whole table. And in the machine learning course, some models use it to find nearby points in the data quickly.

What you learned

Do you really need to check every value when the list is sorted? No.

• Binary search compares the target with the middle of the range, and keeps only the half that can still contain it.
• lo and hi mark the range, and the search ends when it finds the value, or when lo passes hi.
• Because every comparison halves the range, it takes O(log n) comparisons, which is at most twenty for a million values.
• It only works on a sorted list, and it cannot check that for you. Sorting is O(n log n), so it is worth it when you search many times.
• In practice, the bisect module does it for you, with bisect_left giving the index where a value would go, which is how you found where day thirty starts.

Your challenge

In the recursion lesson, a function called itself on a smaller version of the problem. So write binary search that way.

Your function takes lo and hi as parameters, and calls itself on one half, with lo passing hi as the base case. For a list of 1,024 numbers, it should make at most eleven calls for any value in the list.

Binary search takes O(log n), but it needs sorted data. In the sets lesson, checking whether a value was in a set took about the same time however big the set grew, without sorting anything at all. So how does a set find a value without searching? In the next lesson, you will build one by hand, and find out.