GCSE · Computer Science · Edexcel · Spec 1CP2

Linear search

Nine cups, one hidden number, and you can only lift one cup at a time. Where do you start — and how many cups might you have to lift?

Open the cups

Find 126, one cup at a time

Nine cups sit in a row, in no particular order, and each one hides a number. Step through the search and watch which cups get opened — and which ones never do.

Before each click, ask yourself: is this the cup? And how many comparisons have we made so far?

 1  search item = 126
 2  start at cup 1
 3  compare the number in this cup with the search item
 4  if they are equal → stop: found it
 5  if not → move to the next cup, then back to line 3
 6  if there are no cups left → stop: it is not in the list

Variables

cups=▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢ ▢comparisons=0search item=126

Output

Step 1: Nine closed cups in a random order. We're hunting for 126, and we can't see inside a cup until we open it.

1 / 9

Press Next to open the next cup. ▢ is a cup nobody has opened yet.

Step 1 of 9: Nine closed cups in a random order. We're hunting for 126, and we can't see inside a cup until we open it..

Watch out: The search never peeks ahead. It only ever knows what's in the cups it has already opened.

Your turn

Now search a list of words

The list is Moscow, Sydney, Beijing, Athens, Mumbai, Tokyo, Prague, and the search item is Mumbai. The search has started. You choose each missing step.

The search item is Mumbai. Start at the first item in the list, Moscow.
Compare Moscow with Mumbai. They're not equal, so move to the next item, Sydney. (1 comparison)
missing step

Which line is step 3?

Compare Sydney with Mumbai. They're not equal, so move to the next item, Beijing. (2 comparisons)Skip Sydney: it doesn't start with M, so it can't be Mumbai. Move straight on.Stop: the item after Moscow isn't Mumbai either, so Mumbai isn't in the list.

Exam line: Count every comparison, including the one that finds the match.

What do you think?

Will a linear search work here?

Sam's music app keeps 200 song titles in the order they were added, not in alphabetical order. Sam wants to use a linear search to find a song called 'Neon Rain'.

Which is closest to what you think right now?

It won't work yet. The titles need sorting into alphabetical order first.It won't work. A linear search compares numbers, and song titles are words.It will work, and if the song isn't in the first 100 titles, Sam can stop there.It will work, but to be sure the song isn't there, Sam must check all 200 titles.

How sure are you?

I'm sureI think soI'm guessing

It won't work yet. The titles need sorting into alphabetical order first.

This is a common misconception

A linear search doesn't care about order. It looks at every title in turn, so a jumbled list is no problem — remember, the cups were in a random order too. In fact, when a list isn't in order, a linear search is the only reasonable way to search it.

It won't work. A linear search compares numbers, and song titles are words.

This is a common misconception

Each comparison asks one question: is this item equal to the search item? You can ask that about words just as easily as about numbers — it's exactly what you did with Mumbai. A linear search works on a list of any type of data.

It will work, and if the song isn't in the first 100 titles, Sam can stop there.

This is a common misconception

Careful. The titles aren't in any order, so 'Neon Rain' could be title 101, or title 200. Stopping halfway could miss it. The search can only say a song isn't in the list after it has checked every single title.

It will work, but to be sure the song isn't there, Sam must check all 200 titles.

This matches the evidence

Exactly right. Order doesn't matter, and neither does the type of data. What does matter is that 'not in the list' is only allowed once the last item has been checked.

Any order, any type of data — but 'not found' is only allowed after every item has been checked.

How long does it take?

Best case and worst case

The list is Dublin, Cairo, La Paz, Seoul, New York, London, Paris. Drag each search item to the number of comparisons a linear search makes before it stops. (Berlin isn't in the list.)

Place DublinPlace SeoulPlace ParisPlace Berlin

Put it in writing

Explain it like an expert

A club stores the names of its 30 members in a list, in the order they joined — not in alphabetical order. (a) Describe how a linear search would find one member's name in this list. (b) Explain why a linear search is a suitable choice for this list. (c) State the best case and the worst case for this search. [5 marks]

Your answer

0 words · your answer stays on this page and is not sent anywhere.

The mark scheme

(a) It starts at the first name and compares each name in turn with the search item, one after another. (1 mark)
(a) It stops as soon as the name at the current position is equal to the search item. (1 mark)
(b) The list isn't in order, and a linear search works on a list in any order, so it's the only reasonable way to search it. (1 mark)
(c) Best case: the name is the first in the list, so only 1 comparison is needed. (1 mark)
(c) Worst case: the name is the last in the list, or not in the list at all, so all 30 names are compared. (1 mark)

Model answer

(a) The search starts with the first name and compares it with the name being searched for. If they don't match, it moves on to the next name, and so on, one name after another. It stops as soon as it finds a name equal to the search item. (b) The names aren't in alphabetical order. A linear search doesn't need the list to be in any order, so it's the only reasonable way to search this list. (c) The best case is when the name is the first one in the list: 1 comparison. The worst case is when the name is the last one, or isn't in the list at all: all 30 names have to be compared.

The words that earn marks: 'one after another', 'stops when equal', 'any order', and both halves of the worst case — last item OR not in the list.

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Check every item, one after another, until you find what you're looking for — or run out of list.

What you need to know

Describe what a linear search does, step by step, and when it stops.
Carry out a linear search on a list of numbers or strings, counting the comparisons.
Explain why a linear search works on a list in any order, and why it suits unordered lists.
Identify the best case and the worst case, and how many comparisons each one needs.

The big picture

A linear search checks a list one item at a time, starting from the first, comparing each item with the search item. It stops the moment they're equal, and it can only say 'not in the list' once every item has been checked. It works on any order and any type of data, so for an unordered list it's the only reasonable choice. Best case: the first item, 1 comparison. Worst case: the last item or a missing one, every item compared.

Key points

1A linear search looks for a search item by examining each item in a list, one after another, starting from the first.

2At each position, compare the current item with the search item: if they're equal, stop; if not, move to the next item.

3The search can only report that the item is not in the list after every item has been checked.

4It works on lists in any order, sorted or unsorted, and on any type of data, including strings. For an unordered list, it's the only reasonable way to search.

5The performance of an algorithm relates to the number of steps it takes to complete. For a linear search, count the comparisons.

6Best case: the search item is the first item, so 1 comparison. Worst case: it's the last item or isn't in the list, so every item is compared.

.we-_R_18slubsnpfiv5ubrb_ [data-we-step]{display:flex !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-solution]{display:block !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-reveal]{display:none !important}

Worked example

Problem

A list holds eight playing cards in this order: four, ten, five, two, eight, seven, nine and three of spades. Use a linear search to look for the six of spades. How many comparisons are made, and what is the result?

⚠ Watch out

Giving up early. If the item hasn't turned up yet, it's tempting to say it isn't there — but the list can be in any order, so it could be the very last one. 'Not in the list' is only true once every item has been compared.

🧠

Memory hook

Lift, look, move on. Stop the moment you find it — but you can't say 'it's not here' until you've lifted the very last cup.

✓

Check yourself

List: 15, 8, 42, 3, 27. How many comparisons to find 3? And to search for 50? (4 — 3 is the 4th item. 5 — 50 isn't there, so every item is checked.)

Flashcards

(14)

What is a linear search?

An algorithm that searches for an item in a list by examining each item, one after another, to see if it's the item being searched for.

What is the 'search item'?

The item the search is looking for — each item in the list is compared with it.

Where does a linear search start?

At the first item in the list.

What happens at each position in a linear search?

The item at the current position is compared with the search item. If they're not equal, the search moves to the next item.

When does a linear search stop if the item is in the list?

As soon as the item at the current position is equal to the search item. Nothing after it is checked.

A search item is missing from the list. How does the search find that out?

It compares every item right to the end. Only when none of them matched can it report 'not in the list'.

Does a linear search need a sorted list?

No. It works on a list in any order, sorted or unsorted.

Why is linear search used on an unordered list?

If a list isn't in order, a linear search is the only reasonable way to search through it.

Can a linear search look for words (strings)?

Yes. It works on lists containing any type of data, not just numbers.

What does the performance of an algorithm relate to?

The number of steps it takes to complete. For a linear search, count the comparisons.

Linear search: best case?

The search item is the very first item in the list, so only 1 comparison is needed.

Linear search: worst case?

The search item is the last item, or isn't in the list at all, so the whole list is checked.

Worst case for a list of 50 items: how many comparisons?

50 — every item is compared.

Give two everyday jobs where a computer searches data.

Finding a file with a particular name, and finding websites that match some keywords.

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

Find 126, one cup at a time

Now search a list of words

Will a linear search work here?

Best case and worst case

Explain it like an expert

More Edexcel GCSE Computer Science topics