Worksheet

F5.6 Binary search

Algorithms · GCSE · OCR J277 2.1.3, AQA 8525 3.1.3, Edexcel 1CP2 1.2.6 · about 15 min

What this lesson is about

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

• The algorithm
• Hear it halve
• Why it needs sorted data

Questions 5 marks in all

1. [1 mark]What must be true of a list before binary search can be used?

   1. AIt must be sorted
   2. BIt must be short
   3. CIt must hold numbers only
   4. DIt must have an even number of items

2. [1 mark]Binary search on a sorted list of 1,000 items. What is the most checks it needs?

3. [1 mark]Binary search looks for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], checking index 4 (16) first. What happens next?

   1. AIt discards 16 and everything before it, and searches the upper half
   2. BIt discards the upper half
   3. CIt checks index 5 next, then 6, then 7
   4. DIt starts again at index 0

4. [1 mark]Why might a programmer use linear search instead of binary search?

   1. AThe data is not sorted
   2. BLinear search is always faster
   3. CBinary search cannot find numbers
   4. DBinary search needs more memory

5. [1 mark]What does this program print?

   low, high = 0, 9
   mid = (low + high) // 2
   print(mid)

The 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? "))

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/f5-6-binary-search/
The simulator checks it and tells you when it passes. Nothing to install, no account.

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?