Search Party

The mission 🔍

Two lists. One target. Your job: find it in as few checks as possible. There are two classic ways to search — **linear search** and **binary search** — and knowing *when* each one wins is worth easy marks in Paper 1.

Linear search: check them all

**Linear search** starts at the first item and checks each one in turn until it finds the target (or runs out). • Works on **any** list — sorted or not • Simple, but can be slow: a list of `n` items may need up to `n` checks It is like scanning a shuffled deck for the Ace of Spades, one card at a time.

Quick check

You linear-search an unsorted list of 8 scores for one that turns out to be last. Worst case, how many items do you check?

• 1
• 4
• 8
• 64

Binary search: keep halving

**Binary search** only works on a **sorted** list — but it is fast. Each step: 1. Check the **middle** item 2. Target higher? Throw away the bottom half. Lower? Throw away the top half 3. Repeat on what is left Searching `1 3 4 7 9 11 15` for `11`: middle is `7` → too low, keep `9 11 15` → middle `11` → **found in 2 checks**.

Your turn: perform it

An interactive activity.

Fill the gaps

Binary search checks the _____ item, discards _____ the list, then repeats on what is left.

The one catch ⚠️

Binary search’s speed comes with a rule you **must** remember: The data has to be **sorted** first. On an unsorted list, binary search can skip straight past the target. The classic exam slip-up is forgetting this — or miscounting the **middle** and going off by one.

Which one works?

A list of exam scores is in a random order. Which search can find a value WITHOUT sorting the list first?

• Linear search
• Binary search
• Neither can

Why binary flies 🚀

Every step of binary search **halves** what is left, so the number of checks grows very slowly: • `1,000` items → about `10` checks • `1,000,000` items → about `20` checks Linear search on a million items could need a **million** checks. That gap is why sorted data is worth it.

True of binary search?

Pick the TWO statements that are true of binary search.

• It needs the data to be sorted
• It halves the search space each step
• It checks every item in order
• It works on unsorted data

Match them up

In the exam 🎯

Grade-9 habits for this topic: • **Compare** means both sides, like-for-like: linear works on any data but is slower; binary is faster but needs sorted data. • If asked to *perform* binary search, **show the middle item and the half you discard** at every step. • Watch the classic mix-ups: linear vs binary, and **sorted vs unsorted**.

Last one

Your phone contacts are stored A–Z. Which search finds “Zara” in the fewest checks?

• Binary search
• Linear search
• Neither — names cannot be searched