Year 7 · Summer 1
Scratch II: Subroutines and lists · Lesson 3 of 5
Linear search through a list
UnpluggedTopic 12 Searching and sorting
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
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.
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Success criteria
You have got it when you can say:
- 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.
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Retrieval starter
Questions from before. Write your answers, then show them.
- Last lesson
x ← 4, then x ← x × 2, then x ← x + 1. What is x?
A 8B 9C 12
B. 9
- Last unit
The Tube map leaves out real distances. That's…
A AbstractionB DecompositionC Pattern recognition
A. Abstraction
- Earlier this year
A 400 MB file on a 100 Mbps line takes at best…
A 32 secondsB 4 secondsC 40 seconds
A. 32 seconds
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Key words (1 of 2)
- 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.
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Key words (2 of 2)
- Merge sort
- Split into single items, then merge back in order.
The explanation · step 1 of 2
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.
The explanation · step 2 of 2 · part 1 of 2
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.
The explanation · step 2 of 2 · part 2 of 2
Binary search (continued)
| Items | Linear (worst) | Binary (worst) |
|---|---|---|
| 10 | 10 | 4 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
Why so fast? Each check halves the list. Doubling the list only adds one check. (2¹⁰ = 1,024 and 2²⁰ ≈ 1 million.)
The explanation · step 2 of 2
The maths: Most checks binary search can need
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Try it: Binary search, step by step
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Quick quiz · 1 of 3
A linear search on 50 unsorted items, looking for something that is not there, makes…
- A 1 check
- B 25 checks
- C 50 checks
C. 50 checks
It can only say 'not found' after checking every item: the worst case, n = 50.
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Quick quiz · 2 of 3
Bubble sort compares…
- A The first and last items
- B Random pairs
- C Neighbours
C. Neighbours
Items next to each other, swapping them if they're in the wrong order.
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Quick quiz · 3 of 3
During bubble sort, a whole pass makes no swaps. This means…
- A Do one more pass to be safe
- B Start again from the beginning
- C The list is sorted: stop
C. The list is sorted: stop
No pair was out of order, so the whole list is in order. This is the early stop.
Year 7 · Scratch II: Subroutines and lists · Lesson 3 of 5
Exit ticket
Answer on paper before you go. Then check.
Which sort splits the list into single items first?
A Insertion sortB Merge sortC Bubble sort
B. Merge sort Split until every piece has 1 item, then merge back in order.
Insertion sort is especially quick when the list is…
A Nearly sortedB In reverse orderC Very long
A. Nearly sorted Each item only slides as far as it needs. Nearly sorted means hardly any shifting.