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 search through a list
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 Thinking ProgrammingCambridge Lower Secondary Computing 0860
You will learn to
- Carry out a linear search by hand, checking each item in turn.
- Explain why a list of 30 can need up to 30 checks.
- Create a Scratch linear search using a loop and an if.
Success criteria
- I can find a name in a pile of 30 cards and count my checks.
- I can explain why the worst case for 30 items is 30 checks.
- I can make a Scratch script that says whether a name is in a 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.