GCSE · Computer Science · AQA · Spec 8525

Compare linear and binary search

You don't find a word in a dictionary by reading from 'aardvark'. You open it near the middle and jump, which only works because it's in order.

Computer Science · Searching

Two ways to find 38

One sorted list, searched twice. Keep an eye on the comparisons count and the output at the bottom.

Before you press Next: which search will find 38 in fewer comparisons, and roughly how many fewer?

 1  LINEAR: check each item in turn
 2    not 38 → move to the next item
 3    38 → found, stop
 4  BINARY: compare with the mid-point
 5    38 → found, stop
 6    38 > mid → keep the right half
 7    38 < mid → keep the left half

Variables

list=4 9 15 22 31 38 47comparisons=0

Output

Step 1: Here's our list, already in order, smallest first. Both searches will hunt for the same number: 38. Linear search goes first, and it starts at the very front.

1 / 10

Step with Next, or press Play. The · marks are items binary search has thrown away.

Step 1 of 10: Here's our list, already in order, smallest first. Both searches will hunt for the same number: 38. Linear search goes first, and it starts at the very front..

Watch out: Binary search could throw away the left-hand side only because the list was in order. Hold on to that thought: it matters in a minute.

Your turn to check

Where does this binary search go wrong?

A student traces a binary search for 17 in this list, which is in order (smallest first): 2 5 8 13 17 21 26. Their search ends by saying 17 isn't there. Find the line where it goes wrong.

A student's trace — which line goes wrong?

7 items in play: 2 5 8 13 17 21 26. The mid-point is the 4th item, 13.
17 is bigger than 13, so discard 13 and everything before it. In play: 17 21 26.
The mid-point is 21. 17 is smaller than 21, so discard 21 and 17. In play: 26.
The mid-point is 26. 17 is smaller than 26, so discard 26. Nothing is left in play.
No items left to check, so 17 is not in the list.

Predict, then check

Same seven numbers as before, but jumbled.

The list is now 31 4 47 22 9 38 15, not in order. A binary search looks for 9, which is definitely in the list. What happens?

Linear vs binary: side by side

Linear searchvsBinary search

Start with the top row. It decides most questions about which search to use.

Focus

Does the data need to be in order?

Linear search

No. It works on data in any order.

Binary search

Yes. It can only be used on an ordered list.

The insight

Jumbled data? Use linear search, or sort the data first and then use binary search.

How it works through the list

Linear search

Checks each item one at a time, from the start

Binary search

Compares with the mid-point, then discards half of the remaining data, and repeats

Best case and worst case

Linear search

Best: the item is the very first one. Worst: it is the last one, or not in the list at all, so every item is checked.

Binary search

Starts at the mid-point, not the front, so an item being first in the list gives it no head start.

What data it can search

Linear search

Lots of different types of data, including strings

Binary search

Only a data set that has already been sorted

Speed on average

Linear search

Slower on average: each comparison rules out one item

Binary search

Quicker on average: each comparison rules out half of what's left

What do you really think?

Is binary search just the better algorithm?

A friend says: "Binary search is faster, so it's simply the better algorithm. Why would anyone bother with linear search?"

Which idea is closest to what you think right now?

Binary search is always the better choice. Linear search is just the slow version.Linear search only works on numbers, so for words you'd need binary search.Binary search looks through both halves of the list, so it never misses anything.Binary search is quicker on average but only works on ordered data. Linear search works on any order.

How sure are you?

I'm sureI think soI'm guessing

Binary search is always the better choice. Linear search is just the slow version.

This is a common misconception

Binary search is quicker on AVERAGE, and 'on average' is not 'always'. Search the sorted list 4 9 15 22 31 38 47 for 4: linear search finds it with 1 comparison, while binary search needs 3 (22, then 9, then 4). And on a jumbled list binary search can't be trusted at all. Linear search earns its place by working on data in any order.

Linear search only works on numbers, so for words you'd need binary search.

This is a common misconception

Linear search can be used on lots of different types of data, including strings. It simply checks each item in turn to see if it's the one you want, and that works for names and words as well as numbers. Binary search, meanwhile, would need those words sorted first.

Binary search looks through both halves of the list, so it never misses anything.

This is a common misconception

That's exactly what it doesn't do. After each comparison it discards half of the remaining data and never looks there again. That's the source of its speed, and it's why a jumbled list can make it miss an item that is really there.

Binary search is quicker on average but only works on ordered data. Linear search works on any order.

This matches the evidence

Yes, that's the whole trade-off. Binary search is usually faster but needs the data in order. Linear search checks one item at a time, so it's slower on average, but it works on data in any order, strings included.

Pick the search that fits the list. Already in order? Binary search is usually quicker. Not in order? Linear search, or sort the data first.

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

One checks every item in turn. The other throws away half the list with each comparison, but only if the list is in order.

What you need to know

A linear search checks each item in a list one at a time, starting from the first.
A linear search works on data in any order, and on lots of types of data, including strings.
Linear search best case: the item is the very first one. Worst case: it is the last one, or not in the list at all, so every item is checked.
A binary search compares the search item with a mid-point, discards half of the remaining data with each comparison, and repeats until the item is found.
A binary search can only be used on an ordered list. With unordered data, use a linear search or sort the data first.
On average, a binary search finds an item in less time than a linear search.

The big picture

A linear search checks each item in a list one at a time, so it works on data in any order, including strings. A binary search compares the item with a mid-point and discards half of the remaining data with each comparison. That makes it quicker on average, but it can only be used on an ordered list.

Key points

1Linear: one item at a time, from the front, in any order.

2Binary: compare with the mid-point, throw away half, repeat.

3No order, no binary search: use linear search or sort the data first.

4Linear search is quickest when the item is first and slowest when it is last or missing.

5Binary search wins on average, not on every single search.

.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 these names, in this order: Priya, Tom, Aisha, Leo, Maya. Choose a suitable search to find Leo, trace it, and give the best and worst case for this list.

⚠ Watch out

Forgetting that 'not in the list at all' is a worst case for linear search too. The search can't stop early: it has to check every item before it can say the item isn't there.

🧠

Memory hook

Linear walks the line. Binary chops it in half, but only if the line is in order.

✓

Check yourself

Without looking back, explain in two sentences why binary search can throw away half the list after one comparison, and what would stop that from working.

Flashcards

(11)

What does a linear search do?

Checks each item in a list one at a time, starting from the first, until it finds the item.

Does a linear search need the data to be in order?

No. It works on data in any order.

What types of data can a linear search be used on?

Lots of different types, including strings (text such as names and words).

When does a linear search make its fewest comparisons, and when its most?

Fewest: the item sits right at the front. Most: it sits at the very end, or is missing entirely.

What does a binary search do?

Compares the search item with a mid-point, discards half of the remaining data, and repeats until the item is found.

What must be true of a list before you use binary search?

It must be in order (sorted).

Why does binary search need ordered data?

It uses the mid-point to decide which half the item must be in. That only works if smaller items are on one side of the mid-point and bigger ones on the other.

Your data is unordered. What are your two options?

Use a linear search, or sort the data first and then use a binary search.

List in order, smallest first. The search item is bigger than the mid-point. What gets discarded?

The mid-point and everything before it. The search carries on in the right-hand half.

Which search is quicker on average, and why?

Binary search. Each comparison discards half of the remaining data, while linear search rules out one item at a time.

Is binary search quicker on every single search?

No, only on average. If the item is first in the list, linear search finds it straight away.

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

Two ways to find 38

Where does this binary search go wrong?

Is binary search just the better algorithm?

More AQA GCSE Computer Science topics