KS3 · Computer Science

Linear vs binary search

Looking up 'penguin' in a dictionary, you don't read from page one. You open it near the middle, see where you've landed, and jump. That's a search algorithm in disguise.

Computing · Searching algorithms

Binary search: check the middle, bin half

A sorted list of 15 numbers, and we're hunting for 45. Step through and watch the list shrink. A dot (·) is an item that has been thrown away.

Before you press Next: guess how many checks it will take to find 45.

 1  Start with the whole sorted list
 2  REPEAT
 3    Check the middle item of what is left
 4    IF middle item = target THEN stop: found it
 5    IF target < middle item THEN bin the middle item and everything above it
 6    IF target > middle item THEN bin the middle item and everything below it
 7  UNTIL target found OR nothing is left

Variables

checks=0target=45middle item=—still in play=3 7 11 15 19 24 28 32 37 41 45 50 56 61 68

Output

Step 1: Here's the sorted list: 15 numbers, smallest to biggest. We want 45. No checks yet — so how would you start?

1 / 9

Press Next to go one step at a time, or Play to watch it run. Every value is written into the lesson — the page isn't running any code.

Step 1 of 9: Here's the sorted list: 15 numbers, smallest to biggest. We want 45. No checks yet — so how would you start?.

Computer Science · Algorithms

Trace table — dry run the code

Same list, same target, the other way: start at the front and check every item in turn. Watch the checks column.

1Start at the first item
2REPEAT
3 Check this item
4 IF item = target THEN stop: found it
5 Move on to the next item
6UNTIL target found OR the end of the list is reached
position
item
is it 45?
checks
Output
Press Start to run the first line.
·

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

Computing · How many checks?

Now make the list much longer

A sorted list has 1,000 items. At most, how many checks could a binary search ever need — to find any target, or to be sure it isn't there?

Your estimate

500 checks

0 checks1000 checks

Two algorithms, one job: linear vs binary

Linear searchvsBinary search

Start with the top row — it's the one people forget.

Focus

Does the list need to be sorted?

Linear search

No. It works on any list, sorted or unsorted.

Binary search

Yes. It only works on a list that is already sorted.

The insight

Binary search decides which half to bin by comparing the target with the middle item. That only works if smaller items sit below the middle and bigger ones above. On a jumbled list, the target could be in the half it bins.

How does it check items?

Linear search

One after another, starting from the first item.

Binary search

Always the middle of what is left, then it bins the half that can't hold the target.

Worst case as the list gets longer

Linear search

Has to check every item, so the checks grow in step with the length. Double the list, double the checks.

Binary search

Each check bins about half, so doubling the list adds only about one more check.

How simple is it?

Linear search

Very simple to write: start at the front and keep going.

Binary search

More to keep track of: where the middle is, and which part is still in play.

Computing · Choosing a search

So which search should you use?

Choose a branch at each level to reach a decision.

Is the list sorted? → What kind of job is it?

4 situations.

On You need to find an item in a list. 2 branches to choose from.

Walk the route that matches your list. For any one list, only one route is true.

Computing · Check your thinking

What do you really think binary search is?

Which of these is closest to what you think right now?
How sure are you?

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Two ways to find something in a list — and why one of them barely slows down when the list doubles

What you need to know

  • What a search algorithm does, and how to count its checks
  • How linear search works, and why it works on any list
  • How binary search works, and why it needs a sorted list
  • Why halving makes binary search so fast on long lists
  • How to choose the better search for a job

The big picture

A search finds whether a target is in a list, and where; we compare searches by counting checks. Linear search checks each item in turn from the first. It works on any list, but may have to check every item. Binary search only works on a sorted list: check the middle, bin it and the half that can't hold the target, repeat. Each check removes about half of what's left, so doubling the list adds only about one more check. On long sorted lists binary search is much faster; for a short list, or an unsorted list searched once, linear search can be the better choice.

Key points

1A search algorithm looks through a list to find whether a target item is there and, if so, where it is.
2Searches are compared by counting checks (comparisons): how many items are looked at before the target is found, or before the search knows it isn't there.
3Linear search starts at the first item and checks each item in turn until it finds the target or reaches the end. It works on any list, sorted or unsorted.
4Binary search only works on a sorted list. It checks the middle item; if that isn't the target, it bins the middle item and the half that can't hold the target, then repeats until the target is found or nothing is left.
5In the worst case linear search checks every item, so its checks grow in step with the list's length. Each binary-search check removes about half of what's left, so doubling the list adds only about one more check.
6Binary search needs the list sorted first, and sorting takes extra work. For a short list, or an unsorted list searched only once, linear search can be the better choice; for a large sorted list searched often, binary search is better.

Worked example

Problem

Use binary search to look for 20 in this sorted list: 4, 9, 13, 18, 22, 27, 31. Which items get checked, and what does the search find?

⚠ Watch out

Binning the wrong half. If the target is bigger than the middle item, it can only be above it: keep the top part, and bin the middle item and everything below. Smaller? Keep the bottom part. Say it as you go: 'bigger — keep the top'.

🧠

Memory hook

Linear walks the line, one by one. Binary splits in two and bins a half — but only on a list that's in order.

✓

Check yourself

No peeking: which search works on an unsorted list? After checking the middle item, what does binary search bin? And when a sorted list doubles, roughly how many extra checks does binary search need?

Flashcards

(13)
What does a search algorithm do?
It looks through a list to find whether a target item is there and, if so, where it is.
How can you compare how efficient two searches are?
Count the checks (comparisons): how many items each looks at before it finds the target or knows it isn't there.
How does linear search work?
Start at the first item and check each one in turn until you find the target or reach the end of the list.
Does linear search need a sorted list?
No. It works on any list, sorted or unsorted.
What must be true before you can use binary search?
The list must already be sorted.
Binary search: which item do you check first?
The middle item of the list.
Binary search: the middle item isn't the target. What do you throw away?
The middle item, plus the half that can't hold the target: everything above it if the target is smaller, everything below it if the target is bigger.
When does a binary search stop?
When the target is found, or when no items are left (so the target isn't in the list).
Linear search, worst case: how do its checks grow with the list's length?
In step with it: it may have to check every item, so double the list means double the checks.
Binary search: what does doubling the length of a sorted list do to the most checks needed?
Adds only about one more check, because each check removes about half of what's left.
Why is it called 'binary' search?
Because each check splits what's left into two parts. It's nothing to do with binary numbers.
When can linear search be the better choice?
For a short list, or for an unsorted list you'll search only once — sorting first would be extra work.
When is binary search the better choice?
For a large sorted list that is searched often.

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 1 October 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.