KS3 · Computer Science

Linear search

Looking for your mate in a jumbled queue? Start at the front, check each face, stop when you spot them. Only at the back can you say they're not there.

Computer Science · Algorithms

Trace table — dry run the code

One list, two searches. First we look for Mo, then for Sam. Step through one comparison at a time and watch how differently the two searches end.

1list ← ["Kai", "Ben", "Zoe", "Mo", "Ada", "Raj"]
2FOR position ← 1 TO 6
3 IF list[position] = target THEN
4 OUTPUT "Found at position ", position
5 STOP
6 ENDIF
7ENDFOR
8OUTPUT "Not in the list"
position
item
target
match?
Output
Press Start to run the first line.
·

Ready when you are — step through one line at a time.

Predict, then check

Think about the exact moment the search stops.

A linear search looks for 5 in the list 8, 5, 12, 5, 3. There are two 5s in it. Which position does the search report?

Computer Science · Searching

Spot where this trace goes wrong

Use a linear search to look for 7 in the list 2, 5, 9, 4, 7. Record each comparison and say what the search reports.

A pupil's trace — which line goes wrong?

Computer Science · Searching

How many checks for a missing name?

A list holds 500 names in no particular order. A linear search looks for a name that is NOT on the list. How many comparisons does it make before it can report 'not in the list'? Slide to your guess, then lock it in.

Your estimate

500 comparisons

0 comparisons1000 comparisons

Computer Science · Searching

Linear search or binary search?

Linear search isn't the only searching algorithm. Binary search is another one. Place each statement: linear search, binary search, both, or neither.

  • A Linear search
  • B Binary search
  1. Tells you whether the target is in the list
  2. Tells you where the target is, if it is there
  3. Works on a list that is not sorted
  4. Needs the list to be sorted first
  5. Checks each item in turn from the first
  6. Is usually much faster on a long sorted list
  7. Can need a comparison for every item in a long list
  8. Puts the items of the list into order

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Check one item at a time until you find it, or run out of list.

What you need to know

  • A searching algorithm finds out whether a target item is in a list and, if it is, where it is (its position). In this lesson we count positions from 1.
  • Linear search starts at the first item and compares each item with the target, one at a time.
  • If the item matches, the search stops and reports the position. If not, it moves on to the next item.
  • Only when the end of the list is reached with no match does it report that the target is not in the list.
  • Linear search works on any list, sorted or not, because it never relies on the order of the items.
  • It is simple but can be slow on long lists: in the worst case (the target is last or missing) every item is checked. On a sorted list, binary search is usually much faster.

The big picture

Linear search looks for a target in a list by checking each item in turn, starting from the first. If an item matches, it stops and reports that position. If it reaches the end with no match, it reports that the target is not in the list. It works on any list, sorted or not, but in the worst case it needs a comparison for every item, so on a long sorted list binary search is usually much faster.

Key points

1Two ways to finish: found (stop at once) or end of list reached (not in the list).
2If the target appears more than once, linear search reports the first match. Later items are never checked.
3A bigger or smaller item tells linear search nothing about what comes next.
4A missing target in a list of n items takes n comparisons.
5A trace records every comparison: the position, the item there, and whether it matched.

Worked example

Problem

A shop's stock list holds the codes 42, 17, 88, 5, 63, in no particular order. Use a linear search to look for 5. Record each comparison and say what the search reports.

⚠ Watch out

Saying 'not in the list' too early. A linear search can only decide the target is missing after it has checked the very last item. A bigger item, a long run of misses or reaching the middle proves nothing, because the list may not be in any order.

🧠

Memory hook

Look, compare, move on. Stop the moment you find it, and never say 'not here' until you've checked the last one.

✓

Check yourself

Trace a linear search for 30 in 10, 40, 20, 50. How many comparisons does it make, and what does it report? (4 comparisons, none match, so: 'not in the list'.)

Flashcards

(12)
What does a searching algorithm find out?
Whether a target item is in a list and, if it is, its position.
Where does a linear search start?
At the first item in the list (position 1).
In linear search, what happens at each step?
The current item is compared with the target. Match: stop and report the position. No match: move on to the next item.
When can a linear search report 'not in the list'?
Only after the last item has been checked and none matched.
The target appears twice in a list. Which position does linear search report?
The first one. It stops at the first match, so it never reaches the second.
Does a list have to be sorted before a linear search?
No. Linear search works on any list, because it never relies on the order of the items.
What is the worst case for linear search?
The target is the last item or is not in the list at all, so every item has to be checked.
A target is missing from a list of 200 items. How many comparisons does linear search make?
200: one for every item.
Why can linear search be slow on a long list?
The number of comparisons in the worst case grows with the length of the list.
What does binary search need that linear search doesn't?
A sorted list.
Long sorted list: which search is usually much faster?
Binary search.
What does each row of a linear search trace record?
One comparison: the position, the item there, the target, and whether it matched.

Tap any card to flip it, or use Study as deck to go through them one at a time. In the full lesson these run as a spaced-repetition deck — you rate each card Hard, Good or Easy and the tricky ones keep coming back until they stick.

Learning with Lightbulb is opening soon

You can use this lesson now. Join the waitlist and we'll let you know when the full Lightbulb experience is ready.

Keep me posted

More KS3 Computer Science topics

See the full KS3 Computer Science curriculum →

How this lesson was checked. This KS3 Computer Sciencelesson was published through Lightbulb Learning's human-designed editorial process — the educational standards, accuracy rules and publication checks it must pass were authored and approved by Philip Halpin. It passed subject-specific assessment, automated educational checks and technical publication verification before going live (publication checks completed 30 September 2026). Published pages are monitored, human spot-checking is ongoing across the lesson library, and anything found wrong is corrected or withdrawn. How our lessons are made and checked. Spotted a mistake? Email hello@lightbulblearning.co and we'll review it.