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 of list. It is like scanning a shuffled deck for the Ace of Spades, one card at a time.

How many checks?

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

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

Binary-search this sorted list for 23. Halve it, one decision at a time.

Put the algorithm in order

Drag the steps of ONE round of binary search into the order you would carry them out.

• Look at the middle item of the list you still have
• Compare it with the target
• Throw away the half that cannot contain the target
• Repeat on what is left, until you find it or nothing remains

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

Count the halvings

A sorted list has 64 items. Each check halves what is left: 64 → 32 → 16 and so on. How many checks does binary search need in the worst case to get down to a single item?

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

Compare them like for like

**Compare** in this topic means both sides on the same points, not a list of good things about one of them. If you are asked to *perform* binary search, **show the middle item and the half you discard** at every step.

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