Halving

Someone thinks of a number from 1 to 100, and after each guess tells you "higher" or "lower". Nobody guesses 1, then 2, then 3. You guess 50, and half the numbers are gone, whatever the answer. That instinct, turned into a careful loop, is one of the most powerful ideas in programming: it finds one item among a million in about twenty looks. It is also a loop that is famously easy to get slightly wrong. This module builds it slowly, and spends most of its time on exactly where the edges are.

Before this, you can: walk two positions inward on a sorted list, and state what stays true while they move; divide and keep the whole part, and loop while a condition holds; count the work a loop does.

By the end you will be able to halve a range, keep its two ends straight, say how many looks a search needs, find the first position that is large enough, and use halving to search for an answer when there is no list at all.

Before you read on, decide what this prints:

low = 1
high = 100
secret = 37
guesses = 0
while low < high:
    middle = (low + high) // 2
    guesses = guesses + 1
    if middle < secret:
        low = middle + 1
    else:
        high = middle
print(low, guesses)

37 7

Seven guesses for a hundred numbers: 50, 25, 38, 32, 35, 37, 36. Notice that it guessed 37 on the sixth try and kept going. This loop does not stop when it happens to hit the number. It narrows the range until one number is left, and that number is the answer. Stopping early is an extra, and the search is easier to get right without it.

Guess the number

The range of numbers still possible runs from low to high, both included. Each turn looks at the middle and asks one question: is the middle less than the secret?

• If it is, the secret is above the middle. Everything from low up to the middle is gone, so low becomes middle + 1.
• If it is not, the secret is the middle or below it. Everything above the middle is gone, so high becomes middle. The middle itself stays in play, because it may be the secret.

Either way, about half of the range is discarded by one question. The loop ends when low and high are the same number, and that is the only number left.

The middle is worked out with //, which drops the fraction, so the middle of 1 and 100 is 50, and the middle of 37 and 38 is 37. Remember that rounding down. It matters in the next section but one.

Low, high and the middle

Searching a sorted list is the same game, with positions for numbers. To find where a target is, look at the item in the middle of what is left. If the target is larger, it can only be to the right. If it is smaller, only to the left.

def find(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

days = [3, 8, 12, 15, 21, 30, 44, 52, 60]
print(find(days, 44), find(days, 3), find(days, 16))

6 0 -1

This version does stop when it lands on the target, and returns the position. If the target is not in the list, it returns -1.

Follow the search for 44. low is 0 and high is 8, so the middle is 4, which holds 21: too small, so low becomes 5. Now the middle of 5 and 8 is 6, which holds 44. Found, in two looks.

Follow the search for 16, which is not there. Middle 4 holds 21: too large, high becomes 3. Middle 1 holds 8: too small, low becomes 2. Middle 2 holds 12: too small, low becomes 3. Middle 3 holds 15: too small, low becomes 4. Now low is 4 and high is 3: they have crossed, nothing is left, and the loop ends.

What stays true

This loop has three details that look arbitrary and are not: <= in the condition, middle + 1, and middle - 1. Change any of them and the search breaks on some input. The way to see why each is right is to say exactly what low and high mean.

In find, they mean: if the target is in the list at all, its position is from low to high, both ends included.

Check the three details against that sentence.

• At the start, low is 0 and high is the last position: the whole list. True.
• values[middle] < target: the target is not at the middle, nor anywhere to its left. So the first position it could be at is middle + 1.
• Otherwise the target is not at the middle, nor to its right, so the last position it could be at is middle - 1.
• The loop goes on while low <= high, because when they are equal there is still one position in play, and it has not been looked at.

The opening program used different details: low < high, and high = middle. It was right too, because its sentence was different: there, the answer was certain to be in the range, the loop stopped when one number was left, and the middle was kept because it might be the answer.

The sentence is one of two things a loop like this needs, and they are separate.

• The sentence stays true. No line may discard a position the target could be at. A line that does gives a wrong answer.
• The range gets smaller on every turn, and the loop stops only when nothing is left to look at. A loop can keep its sentence true and still fail here. Writing low = middle discards nothing it should not, so the sentence holds; but when the middle is low itself the range does not shrink, and the loop goes round for ever. Stopping at low < high also leaves the sentence true, and gives up with one position not yet looked at.

So a broken search has one of four faults: an end that starts outside the list, a line that throws away a position still in play, a stop that comes before the positions run out, or a turn that does not shrink the range. Only the second makes the sentence false.

Both loops above are correct. Mixing them is not. high = middle together with low <= high gives a loop that can go round for ever: when low and high are equal, the middle is that same position, high is set to it again, and nothing changes. Nearly every broken halving loop is two correct ones mixed. Decide what your two ends mean, write it down as a comment, and check each line against it.

How many looks?

Each look halves what is left. Count how many times a number can be halved before 1 is reached:

def halvings(n):
    count = 0
    while n > 1:
        n = n // 2
        count = count + 1
    return count

print(halvings(8), halvings(1000), halvings(1000000))

3 9 19

A list of a thousand items is searched in about ten looks. A million takes about twenty. A thousand million takes about thirty. Multiplying the size of the list by a thousand adds ten looks.

Compare that with reading the list from the start, which for a million items takes half a million looks on average when the target is there and equally likely to be anywhere, and the full million when it is not there. That is the reward for the list being sorted. It is also the cost: the list has to be kept sorted, and halving on a list that is not sorted is not slow, it is wrong.

The first that is large enough

find answers "where is 44?". Often the more useful question is a little different: where is the first item that is at least 16?

For the list above that is position 4, the 21. That one answer tells you three things. 16 is not in the list, because the item there is not 16. If 16 were to be added, position 4 is where it would go to keep the list sorted. And exactly four items are smaller than 16.

When the target appears several times, the same question finds the first of them, which find does not promise: it returns whichever one it lands on.

Look at the last row. When no item is large enough, the answer is the length of the list: the position just past the end. So the range of possible answers is one longer than the range of positions, and a loop for this question has to start with that in mind.

A loop for this question never stops early on a match, because an equal item might not be the first one. It is the opening program's shape, not find's: narrow the range until one position is left. The lab asks you to write it, and to say what your two ends mean before you do.

Searching for an answer

The guessing game had no list. It had a range of possible answers and a way to test a guess. That is all halving needs, and it makes the idea far wider than searching.

What is the largest whole number whose square is not more than 2,000? You could try 1, 2, 3 and so on. Or you can notice that the test "is the square of this number at most 2,000?" is true for every small number and false for every large one, with one changeover between them, and halve towards the changeover.

def whole_root(n):
    low = 0
    high = n
    while low < high:
        middle = (low + high + 1) // 2
        if middle * middle <= n:
            low = middle
        else:
            high = middle - 1
    return low

print(whole_root(2000), whole_root(49), whole_root(1000000))

44 7 1000

low and high mean: the answer is from low to high, both included. If the middle passes the test, the answer is the middle or larger, so low = middle. If it fails, the answer is smaller, so high = middle - 1.

There is one new detail: (low + high + 1) // 2. Here the line that keeps the middle is low = middle. If the middle were rounded down, then with low at 44 and high at 45 the middle would be 44, low would be set to 44 again, and the loop would never end. Rounding up makes the middle 45, so the range always shrinks. The rule: whichever end can be set to the middle itself, round the middle away from it.

Halving works on answers whenever two things are true. You can test a guess. And the guesses that pass are all on one side of those that fail, with no mixing. Then you do not need to find the answer by cleverness. You need only be able to check one, and the halving finds it in a few dozen tries.

In the lab

You will play the guessing game by hand, follow low and high through a search, and count the looks a million items need. You will write the search again for a list sorted the other way, write the first position that is large enough, and count how often a value appears without walking along it. Then you will search for an answer: the smallest van that can do a job in a given number of trips. Four assignments follow: the top of a hill, a search with two mistakes, the nearest price, and one problem that does not tell you to halve.