Find it fast — or find it slow?
Year 9 Computer Science — Binary Search
Guess it. I'll tell you HIGHER or LOWER.
How many guesses will you need?
Linear search: Guess 1, then 2, then 3... up to 100. Worst case: 100 guesses.
Binary search: Always guess the MIDDLE of the remaining range. Worst case: 7 guesses.
Binary search is roughly 14× faster for 100 items. For 1,000,000 items: 50,000× faster.
Each guess halves the remaining range.
Midpoint formula: (low + high) ÷ 2, rounded down.
Teacher thinks of a number 1–100.
Class guesses: 1, 2, 3, 4, 5... raise hands in order.
Count every guess. Record the total.
(This might take a while. That's the point.)
Play in pairs. One thinks, one guesses using binary search.
Always guess the exact midpoint — no intuition!
Play 5 rounds. Record guesses each time.
Complete Part 2 and 3 on your worksheet.
Binary search worst case for various list sizes:
Double the list size → only 1 more guess.
Binary search only works if you can say "the answer is definitely in the HIGHER half."
If the list isn't sorted, you can't discard any half — you might be wrong.
Unsorted list → must check every item → linear search.