Linear search
Linear search: check every item from the start until you find it.
- Works on any list, sorted or not.
- Simple.
- Slow on long lists: a million items may need a million checks.
Linear vs binary search with numbered cards
UnpluggedPresent ▶
What this lesson covers
Topic 12 Searching and sorting
KS3 Computing · Searching finds an item. Sorting puts items in order. Some algorithms are hugely faster than others on big lists, and the difference grows as the list grows.
Computational ThinkingCambridge Lower Secondary Computing 0860
You will learn to
- Carry out a linear search on cards, checking each one in turn.
- Carry out a binary search on sorted cards: check the middle, then throw away half.
- Explain why binary search only works on a sorted list.
- Compare the checks each search needs, using the binary search toy.
Success criteria
- I can find 17 in twenty sorted cards both ways, and count my checks.
- I can explain why binary search needs at most 5 checks for 20 cards.
- I can choose the right search for a sorted list and for an unsorted list.
Key words
Say each word, then read what it means. Every one is in the glossary too.
- Linear search
- Check every item in turn.
- Binary search
- Search a sorted list by halving it each step.
- Bubble sort
- Swap neighbours until a whole pass makes no swaps.
- Insertion sort
- Slide each item into its place in the sorted part.
- Merge sort
- Split into single items, then merge back in order.
The explanation
Read it here, or open the study page below to go one step at a time with things to try.
Binary search
Binary search needs a sorted list. Like a dictionary: open in the middle, throw away the wrong half, repeat.
- Look at the middle item.
- Is it the one? Stop.
- Is your item bigger? Throw away the left half. Smaller? Throw away the right half.
- Repeat with what's left.
| Items | Linear (worst) | Binary (worst) |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
?Why?
Why so fast? Each check halves the list. Doubling the list only adds one check. (2¹⁰ = 1,024 and 2²⁰ ≈ 1 million.)
Study it
Open the study page and go one step at a time.
The steps for this lesson
- Topic 12, step 3: Binary search (Binary search, step by step)
Try it
Check yourself
One question at a time. The reason shows after each answer.
Saved on this device.