GCSE-ready- Home
- Lessons
- KS3 Computing
- Searching: linear and binary search
Searching: linear and binary search
🎬 The doodle video for this lesson is coming soon. Subscribe on YouTube to see it first.
How do you find one item in a list? There are two famous algorithms. One is simple; the other is much faster on big sorted lists.
Linear search
Start at the first item. Check each item in turn until you find the target or reach the end.
It works on any list, sorted or not.
For a list of 1,000 items it might need 1,000 checks.
It works on any list, sorted or not.
For a list of 1,000 items it might need 1,000 checks.
Binary search
Binary search only works on a sorted list.
1. Look at the middle item.
2. If it is the target, stop.
3. If the target is bigger, throw away the left half. If smaller, throw away the right half.
4. Repeat with the half that is left.
Each check halves the list, so even 1,000 items need at most 10 checks.
1. Look at the middle item.
2. If it is the target, stop.
3. If the target is bigger, throw away the left half. If smaller, throw away the right half.
4. Repeat with the half that is left.
Each check halves the list, so even 1,000 items need at most 10 checks.
Example
Find 23 in 3, 8, 12, 17, 23, 31, 40.
Middle item is 17. 23 is bigger, so keep 23, 31, 40.
Middle is 31. 23 is smaller, so keep 23.
Check 23: found after 3 checks. A linear search needs 5 checks.
Middle item is 17. 23 is bigger, so keep 23, 31, 40.
Middle is 31. 23 is smaller, so keep 23.
Check 23: found after 3 checks. A linear search needs 5 checks.
Use binary search to find 9 in 2, 5, 9, 14, 18, 21, 27, 33, 38, 41, 50. Which items are checked?
- 11 items: the middle one is 21. 9 is smaller, keep the left half: 2, 5, 9, 14, 18.
- Middle is 9: found.
Answer: 21, 9
Linear search checks every item in order and works on any list. Binary search needs a sorted list; it checks the middle and halves the list each time, so it is far faster on large lists.
Check you have got it
Answer 6 quick questions with instant marking. If you get one wrong, GCSE-ready shows you why and gives you another go. It is free, and you do not need an account.