Binary search

Halving a sorted list, and why it needs sorted data.

F5.6AlgorithmsGCSE15 min

Think of a number between 1 and 100, and have a friend guess it, saying only "higher" or "lower" after each guess. The best strategy is to guess 50, then 25 or 75, halving the range every time: it never takes more than seven guesses. That strategy is binary search, and it is dramatically faster than checking every item, as long as the items are in order.

The algorithm

On a sorted list:

1. Look at the middle item.
2. If it is the target, stop: found.
3. If the target is smaller, throw away the middle item and everything after it.
4. If the target is bigger, throw away the middle item and everything before it.
5. Repeat on what is left, until the target is found or nothing is left.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def binary_search(items, target):
    """items must be sorted. Return the index of target, or -1."""
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        print("  checking index", mid, "which holds", items[mid])
        if items[mid] == target:
            return mid
        elif target < items[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

ids = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("found at", binary_search(ids, 23))
print("found at", binary_search(ids, 40))

Run this in the simulator

low and high mark the part of the list that could still hold the target. Each check moves one of them past the middle, so the part left roughly halves. When low passes high, nothing is left and the target is not in the list.

Hear it halve

Each check plays a note higher up the scale, so you can hear how few there are. Try targets near the start, the middle and the end:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

numbers = list(range(0, 1000, 5))       # 200 sorted numbers: 0, 5, 10, ... 995
target = 735

low, high, checks = 0, len(numbers) - 1, 0
while low <= high:
    mid = (low + high) // 2
    checks = checks + 1
    tone(300 + checks * 60, 0.15)
    if numbers[mid] == target:
        break
    elif target < numbers[mid]:
        high = mid - 1
    else:
        low = mid + 1
print("found", target, "after", checks, "checks, out of", len(numbers), "numbers")

Run this in the simulator

200 items, and never more than 8 checks. Linear search could need 200. Double the list to 400 and binary search needs just one more check; linear search needs twice as many.

Why it needs sorted data

Binary search throws away half the list based on one comparison. That is only safe if everything smaller than the middle item is before it and everything bigger is after it. On an unsorted list it will confidently say an item is not there when it is. Try it: shuffle the ids list in the first cell and search again.

So binary search has a cost: the data must be sorted first, and kept sorted. Sorting is the next three lessons.

Task: binary search the markers

The task asks Which marker? and answers 56. Using binary search (not in or .index), find it in the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Beep once for every check, and print found 56 at index <i> after <n> checks.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

ids = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = int(input("Which marker? "))

Challenges

1. Play the number guessing game with a partner using binary search. Is seven guesses always enough for 1 to 100?
2. Change binary_search so it returns how many checks it took, and test it on every item of a list.
3. What happens if the list has repeated items? Does binary search still find one of them?