Binary search

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

F5.6AlgorithmsGCSE15 min

Covers OCR J277 2.1.3 Searching and sorting algorithms · AQA 8525 3.1.3 Searching algorithms · Edexcel 1CP2 1.2.6 Standard sorting and searching algorithms

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Linear search and binary search explained

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.

Binary search on the lesson's ten ids: 23 is found on the third check; 40 takes four checks and ends with low past high0123456789indexlooking for 2325812162338567291low 0, high 9: mid 423 > 16, so low = 525812162338567291low 5, high 9: mid 723 < 56, so high = 625812162338567291low 5, high 6: mid 523 is it: found at 5looking for 4025812162338567291low 0, high 9: mid 440 > 16, so low = 525812162338567291low 5, high 9: mid 740 < 56, so high = 625812162338567291low 5, high 6: mid 540 > 23, so low = 625812162338567291low 6, high 6: mid 640 > 38, so low = 7low 7 is now past high 6: nothing is left, so the answer is -1
Each row is one check. The bold box is the middle, and the dashed boxes have been thrown away. For 23 the part left goes 10, 5, 2, and the third check finds it. For 40 each check still halves what is left, until low moves past high and there is nothing left to look at.

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.

The part of the 200 numbers that could still hold 735, before each of the 7 checks: 200, 100, 49, 24, 12, 6 and 3 numbers0995735check 1200 leftcheck 2100 leftcheck 349 leftcheck 424 leftcheck 512 leftcheck 66 leftcheck 73 left
Each bar is the part that could still hold 735, and the tick is the middle checked. One check throws away half, so 200 numbers are down to 3 after six checks, and the seventh finds it. Doubling the list would add just one more bar.
Items Linear search, worst case Binary search, worst case
10 10 4
100 100 7
1,000 1,000 10
1,000,000 1,000,000 20

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 can 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?

Past paper questions on this

Real exam questions that test this, each worked through with a program you can run.