Searching algorithms: linear and binary search
A search algorithm finds a target value in a list, or reports that it is not there. You need to describe, trace and compare the two standard ones, and say when each is the better choice.
Part 1 of 3: Learn it
In short
- Linear search checks each item in turn and works on any list.
- Binary search needs the list in order first. Each check looks at the middle item and rules out half of what is left.
- For large sorted lists, binary search needs far fewer comparisons.
Where this is in your specification
Spec points: AQA 3.1.3, OCR 2.1.3, Edexcel Topic 1
| Board | Topic: Algorithms |
|---|---|
| AQA 8525 | 3.1.1 to 3.1.4 |
| Edexcel 1CP2 | Topic 1 |
| OCR J277 | 2.1.1 to 2.1.3 |
| Eduqas C500 | 8 Algorithms and constructs |
| Cambridge IGCSE 0478 | 7 Algorithm design and problem-solving |
| National 5 C816 75 | Software design and development: design, standard algorithms |
Linear search
- Start at the first item.
- Compare it with the target. If they match, stop and report where it is.
- Otherwise move to the next item and repeat.
- If you reach the end with no match, the target is not in the list.
It is simple and the list does not need to be in order, but in the worst case it checks every item: 1000 comparisons for 1000 items.
Binary search
- Look at the middle item of the part of the list still being searched.
- If it is the target, stop.
- If the target is bigger, discard the middle item and everything before it; if smaller, discard the middle item and everything after it.
- Repeat on the half that is left until the target is found or nothing is left.
With an even number of items there are two middles; use the rule your board's pseudocode uses, usually (low + high) DIV 2.
Comparing them
| Linear search | Binary search | |
|---|---|---|
| List must be sorted? | no | yes |
| Worst case for 1000 items | 1000 comparisons | 10 comparisons |
| Good for | short or unsorted lists | long sorted lists |
| Code | very simple | a little harder |
Each step of binary search halves the list, and 2¹⁰ = 1024, so 10 steps are enough for up to 1024 items.
What must be true about a list before a binary search can be used?
Show the answer
It must be sorted.
Part 2 of 3: See it worked
Worked examples
Example 1
Use binary search to find 37 in the list 3, 8, 12, 19, 25, 31, 37, 44, 50 (positions 0 to 8).
- low = 0, high = 8, middle = 4: the value is 25. 37 is bigger, so low = 5
- low = 5, high = 8, middle = 6: the value is 37. Found
Answer: 37 is at position 6, found after 2 comparisons.
Example 2
A list of 500 names is not in alphabetical order. Which search should be used, and what is the most comparisons it could need?
- The list is unsorted, so binary search cannot be used
- Linear search might have to check every item
Answer: Linear search, with up to 500 comparisons.
Common mistakes
- Running a binary search on an unsorted list.
- Saying binary search always beats linear search. For a very short list, or a target near the start, linear can be as quick.
- Forgetting to discard the middle item itself after checking it.
- Describing the steps without saying what happens when the item is not found.
What is the most comparisons a linear search could need for 80 items?
Show the answer
80.
Part 3 of 3: Test yourself
Check yourself
Answer each one in your head or on paper first, then open it to check.
What must be true about a list before a binary search can be used?
It must be sorted.
What is the most comparisons a linear search could need for 80 items?
80.
About how many comparisons does a binary search need, at most, for 1000 sorted items?
10, since 2¹⁰ = 1024.
Jobs that use this
- Software developer (öffnet einen neuen Tab)
- Web developer (öffnet einen neuen Tab)
- Computer games developer (öffnet einen neuen Tab)
Each link opens the job profile on the National Careers Service (England). In the rest of the UK: My World of Work (Scotland), Careers Wales, nidirect careers (Northern Ireland).
Diese Lernzettel sind auf Englisch, weil sie britischen Prüfungslehrplänen folgen.
Full lessons and marked practice for this course are coming soon to Brainlag Learn. See courses