Key Stage 3 computing · Algorithms

KS3 computing: searching algorithms (linear and binary)

A searching algorithm is a set of steps for finding an item in a collection of data. At Key Stage 3, students meet two standard examples, linear search and binary search, learn to follow them by hand and in code, and start to reason about when each is the better choice. Searching is one of the key algorithms the curriculum names as an example of computational thinking.

Searching algorithms, explained

The national curriculum asks Key Stage 3 pupils to understand several key algorithms that reflect computational thinking, with sorting and searching given as examples, and to use logical reasoning to compare alternative algorithms for the same problem. Schools choose which algorithms to teach, but linear and binary search are the usual choices for searching. They make a good pair because they solve the same problem in very different ways.

In a linear search the computer looks at the first item, then the second, then the third, and so on until it finds what it wants or reaches the end. It is simple, and it works on any list, sorted or not. The drawback is that a long list takes a long time: if the item is at the end, or is not there at all, every single item has to be checked. It is the kind of search a person does when running a finger down a short, jumbled list of names.

Binary search is a lot quicker, but it only works if the list is already in order. The computer looks at the middle item. If that is the target, it stops. If the target is smaller, the whole top half of the list can be ruled out, so it carries on with the bottom half; if the target is bigger, it keeps the top half. Each check cuts the remaining list in half, and it repeats until it finds the item or nothing is left. It is a similar idea to looking up a word in a printed dictionary: open it somewhere in the middle and decide which half to keep.

Students are not only expected to follow these steps. They trace the algorithm on paper, often with a table that tracks the position of the first, last and middle items, write it as a flowchart or in pseudocode, and then program it. They also reason about it: how many checks are needed in the best case and the worst case, and why does binary search need sorted data? The comparison between the two methods is covered more generally on the page about comparing algorithms. Formal notation for efficiency is left to later study.

Words your child will hear

Algorithm: A precise, step-by-step set of instructions for solving a problem.
Linear search: Checking each item in turn, from the start, until the target is found or the list ends.
Binary search: Repeatedly checking the middle of a sorted list and discarding the half that cannot contain the target.
Target: The item being looked for.
Index: The position of an item in a list, often starting at 0 in programming.
Midpoint: The position in the middle of the part of the list still being searched.
Trace table: A table used to track the values of variables as an algorithm runs.

What the National Curriculum says

The programme of study for Key Stage 3 says:

Pupils should be taught to understand several key algorithms that reflect computational thinking [for example, ones for sorting and searching]; use logical reasoning to compare the utility of alternative algorithms for the same problem
Aim: pupils can understand and apply the fundamental principles and concepts of computer science, including abstraction, logic, algorithms and data representation.

Objectives from the National Curriculum in England, © Crown copyright, used under the Open Government Licence v3.0.

A worked example

This sorted list has 9 items: 3, 8, 12, 17, 23, 29, 35, 41, 50. Find 41 using linear search and then binary search. Compare the number of checks.

Linear search. Start at the first item and check each one in turn: 3, 8, 12, 17, 23, 29, 35, then 41. The target is found on the eighth check.
```
3 8 12 17 23 29 35 41
1 2 3  4  5  6  7  8
```
Binary search. Number the positions 1 to 9. The search covers positions 1 to 9, so the middle is position 5, which holds 23. The target 41 is bigger than 23, so everything from position 5 downwards can be thrown away. That is one check.
```
Search 1-9, middle 5: 23 < 41
```
Now the search covers positions 6 to 9. The middle of 6 to 9 is position 7 (rounding down from 7.5), which holds 35. 41 is bigger, so positions 6 and 7 go. That is check two.
```
Search 6-9, middle 7: 35 < 41
```
Now only positions 8 and 9 are left. Taking the lower middle, position 8 holds 41. This matches the target, so the search stops. That is check three.
```
Search 8-9, middle 8: 41 found
```
Compare. Linear search took 8 checks and binary search took 3. The gap grows with the size of the list: for a sorted list of a million items, linear search could need up to a million checks, while binary search needs at most about 20.

41 is the eighth item. Linear search needs 8 checks and binary search needs 3, but binary search only works because the list is sorted.

Common mistakes and how to help

Thinking binary search works on any list

Students focus on the halving and forget why halving is allowed. Throwing away half the list only makes sense if the items are in order.

What helps: Try it on a jumbled list and watch it fail: if the middle item is 23 and the list is unordered, 41 could still be on either side. Always ask “is the data sorted?” first.

Thinking the middle item is the average value

The word “middle” can suggest the value halfway between the smallest and the largest, rather than the item in the middle position.

What helps: Stress that the algorithm uses positions, not values. In a list of 3, 4, 5, 6, 100, the middle item is 5 even though the values are far from evenly spread.

Believing binary search is always better

It is often the faster of the two, so students assume it wins every time.

What helps: If the target is the very first item, linear search finds it in one check, and for a short list there is little to gain. On unsorted data binary search cannot be used at all unless the list is sorted first, and sorting takes more work than a single linear search. The choice depends on the situation.

Making off-by-one errors when tracing or coding

With an even number of items there is no exact middle, and students lose track of whether positions start at 0 or 1, or whether the new range includes the item just checked.

What helps: Use a trace table with columns for first, last and middle, and agree a rule for rounding. Test with lists of one, two and an even number of items.

How to help at home

Play higher or lower. Think of a number from 1 to 100 and let your child guess with “higher” or “lower” clues. Ask what the best first guess is. They will discover the halving strategy for themselves.
Look up a word in a paper dictionary. If you have a paper dictionary, ask your child to find a word as quickly as possible and describe what they do. Opening near the middle and deciding which half to keep is binary search.
Search a shuffled and a sorted pack. Take a pack of cards and find a particular card in a shuffled set by checking one at a time. Then sort a few of them into order and find one by halving. Compare how many cards you turned over.
Ask them to explain it in their own words. Ask your teenager to teach you a search as if you were a computer that can only follow exact steps. Explaining the algorithm clearly is better practice than re-reading notes.
Spot the searches in daily life. Finding a contact in a phone, a file on a computer or a product in a shop all involve search. Ask whether the thing you are searching is in order and how that helps.

Builds on

Key Stage 2: Designing, writing and debugging programs
Key Stage 2: Controlling and simulating physical systems
Key Stage 2: Decomposition: breaking problems down
Key Stage 2: Sequence in programs
Key Stage 2: Selection: if and else
Key Stage 2: Repetition and loops
Key Stage 2: Variables, input and output
Key Stage 2: Explaining how algorithms work
Key Stage 2: Debugging algorithms and programs