Cover lesson · Computer Science · Year 11 · Advanced

Tracing search algorithms: linear and binary search

DCF: Data and computational thinking → Problem-solving and modelling

Name: Class: Date:

Cover teacher — you need no subject knowledge and no computers

Print: this sheet, one per pupil, and the stimulus sheet "Search algorithm reference sheet", one per pupil or one between two. It holds the sorted list and all three algorithms. Pupils need only a pen.

Run: 5 min read the reference sheet, especially the rules for tracing · 10 min Step 1, linear search · 10 min Step 2, binary search for 61 · 8 min Step 3, binary search for a missing value · 7 min Step 4, big lists · 10 min Step 5, find the bug · 5 min Step 6, explain.

Collect: this sheet. Every trace table has a single right answer, and all of them are on the worked example sheet, so you can mark in a few minutes. The one to check first is Step 2: 61 is found at index 10 after 4 comparisons.

What you are doing

Exam questions on searching almost always give you an algorithm and ask you to trace it: follow it line by line and record what every variable holds. You are going to trace linear search and binary search on the same sorted list, count how much work each one does, work out what happens when the list gets huge, and then use a trace to find a bug that a quick read would miss.

Step 1 — linear search

Use linearSearch on the reference sheet. For each target, count the comparisons (how many times line 3 runs) and write down what the function returns.

Target	Comparisons made	Value returned	Why that many?
61
4
93
50

Which of those four is the best case and which is the worst case for linear search on a list of 16 items?

Step 2 — binary search for 61

Use Version A. One row per pass of the WHILE loop. Work out mid with DIV every time — do not guess the middle by eye.

Pass	low	high	mid	list[mid]	Compared with 61, so…
1
2
3
4
5

Value returned: ________ Comparisons made: ________ Linear search needed: ________

Step 3 — binary search for a value that is not there

Trace Version A again with target 50. Keep going until the WHILE condition is false, and record the final values of low and high in the last row.

Pass	mid	list[mid]
1
2
3
4
End	—	—

Why does the loop stop, and why is it safe to say 50 is not in the list without looking at every item?

Step 4 — what happens when the list is huge

The worst case for binary search: keep halving the list size, rounding down, until you reach 1. Count the halvings and add 1. For 16: 16 → 8 → 4 → 2 → 1 is 4 halvings, so at worst 5 comparisons. A useful fact: 2¹⁰ = 1,024.

Items in the sorted list	Linear search, worst case	Binary search, worst case
16		5
1,000
1,000,000
3,000,000 — roughly one entry per person in Wales

If the list doubles in size, how many extra comparisons does binary search need at worst? Why?

Step 5 — find the bug in Version B

Version B differs from Version A by one character. (a) Trace Version B with target 61, the value you found in Step 2.

Pass	mid	list[mid]
1
2
3
End	—	—

(b) What does Version B return, and why is that wrong?

(c) Which line holds the error? Write the corrected line.

Line ____ : ________________________________________

(d) Version B still finds 42 on the first pass. Name one other value in the list that Version B fails to find, and explain what all the failures have in common.

Step 6 — explain

(a) Trace Version A on the unsorted list at the bottom of the reference sheet with target 12. What does it return? Use your trace to explain why binary search needs sorted data.

(b) Binary search is much faster, yet linear search is still used. Give two situations where linear search is the sensible choice.

Step by step

5 min — Read the reference sheet. Check you can work out (8 + 15) DIV 2 = 11.
10 min — Step 1: linear search for four targets, then best and worst case.
10 min — Step 2: binary search trace for 61.
8 min — Step 3: binary search trace for 50, which is not in the list.
7 min — Step 4: worst cases for big lists.
10 min — Step 5: trace Version B, find the error and fix it.
5 min — Step 6: the two explanations.

Success criteria

I can trace linear search and count its comparisons, including when the target is missing.
I can complete a binary search trace table, recording low, high and mid on every pass and using DIV correctly.
I can say exactly when binary search stops without finding the target, and what it returns.
I can compare the worst cases of both algorithms as the list grows, and explain why doubling the list adds only one comparison to binary search.
I can use a trace to find a logic error, give an input that exposes it, and correct the line.

If you finish early

Find the average number of comparisons binary search (Version A) needs to find each of the 16 items in the list. Hint: one item needs 1 comparison, two need 2, four need 3, eight need 4 — which item needs 5?
Write Version A as a recursive function: binarySearch(list, target, low, high). What is the base case?
Change line 5 to mid ← (low + high + 1) DIV 2. Does Version A still work? Trace it for 4 and for 93 before you answer.