Worked example · Computer Science · Year 11
DCF: Data and computational thinking → Problem-solving and modelling
A secure Year 11 response, annotated against the success criteria. Every trace table below is the only correct one, so you can mark from it directly. The four numbers to check first: 61 is at index 10, found in 11 linear comparisons and 4 binary comparisons; Version B returns −1 for 61 because line 4 should read WHILE low <= high.
| Target | Comparisons | Returned | Why that many? |
|---|---|---|---|
| 61 | 11 | 10 | 61 is at index 10, and indexes 0 to 10 are 11 items, each checked once. |
| 4 | 1 | 0 | It is the first item, so line 3 is true straight away. |
| 93 | 16 | 15 | It is the last item, so every item is checked. |
| 50 | 16 | −1 | Not in the list. The loop checks all 16 items, finishes, and line 7 returns −1. |
Best case: 4, one comparison, because the target is at the front. Worst case: 93 and 50 both need all 16 comparisons — the last item and a missing item cost the same, because linear search cannot know an item is missing until it has checked everything.
Counts are exact, the "not found" return value is right, and the answer spots that a missing target is also a worst case. Evidences criterion 1.
| Pass | low | high | mid | list[mid] | Compared with 61, so… |
|---|---|---|---|---|---|
| 1 | 0 | 15 | 15 DIV 2 = 7 | 42 | 42 < 61, so low ← 8 |
| 2 | 8 | 15 | 23 DIV 2 = 11 | 68 | 68 > 61, so high ← 10 |
| 3 | 8 | 10 | 18 DIV 2 = 9 | 55 | 55 < 61, so low ← 10 |
| 4 | 10 | 10 | 20 DIV 2 = 10 | 61 | Equal: RETURN 10 |
Value returned: 10. Comparisons: 4. Linear search needed 11 for the same item.
One row per pass, the DIV working written out so a slip can be spotted, and the trace stops on the RETURN rather than running an extra pass. Evidences criterion 2.
| Pass | low | high | mid | list[mid] | Compared with 50, so… |
|---|---|---|---|---|---|
| 1 | 0 | 15 | 7 | 42 | 42 < 50, so low ← 8 |
| 2 | 8 | 15 | 11 | 68 | 68 > 50, so high ← 10 |
| 3 | 8 | 10 | 9 | 55 | 55 > 50, so high ← 8 |
| 4 | 8 | 8 | 8 | 47 | 47 < 50, so low ← 9 |
| End | 9 | 8 | — | — | 9 <= 8 is false: loop ends, RETURN −1 |
The loop stops because low has passed high: there is no part of the list left in play. It is safe because the list is sorted. Everything at index 8 and below is 47 or less, and everything at index 9 and above is 55 or more, so 50 would have to sit between index 8 and index 9 — and there is no such place. Four comparisons proved what linear search needed sixteen to prove.
Records the final low and high, explains the stopping condition, and ties the proof of absence to the list being sorted. Evidences criterion 3.
| Items in the sorted list | Linear, worst case | Binary, worst case, with working |
|---|---|---|
| 16 | 16 | 5 (given) |
| 1,000 | 1,000 | 10: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 is 9 halvings, plus 1 |
| 1,000,000 | 1,000,000 | 20: 219 = 524,288 fits inside a million but 220 = 1,048,576 does not, so 19 halvings, plus 1 |
| 3,000,000 | 3,000,000 | 22: 221 = 2,097,152 fits but 222 = 4,194,304 does not, so 21 halvings, plus 1 |
Doubling the list adds one comparison at worst. The first comparison in the bigger list throws away half of it, which leaves a list the size of the old one. Linear search, by contrast, doubles its worst case every time the list doubles.
All worst cases correct with the halving shown, and the "one extra comparison per doubling" is explained by what the first comparison does, not just stated. Evidences criterion 4.
| Pass | low | high | mid | list[mid] | Compared with 61, so… |
|---|---|---|---|---|---|
| 1 | 0 | 15 | 7 | 42 | 42 < 61, so low ← 8 |
| 2 | 8 | 15 | 11 | 68 | 68 > 61, so high ← 10 |
| 3 | 8 | 10 | 9 | 55 | 55 < 61, so low ← 10 |
| End | 10 | 10 | — | — | 10 < 10 is false: loop ends, RETURN −1 |
(b) It returns −1, "not found", but 61 is at index 10. The search had narrowed down to exactly the right item and then stopped before looking at it.
(c) Line 4 : WHILE low <= high
(d) 93 also fails. Tracing it: low and high close in on 15 and 15, and the loop exits without checking index 15. The full list of failures is 4, 15, 26, 38, 47, 61, 72 and 93 — half the list. What they have in common is that Version A only reaches them when low = high, when the range is down to a single item. Version B refuses to enter the loop for a range of one item, so it never looks at them. 42 works because it is found on the first pass, while the range is still wide.
The trace is what finds the bug, a concrete failing input is given, the fix is exactly one character, and the pattern behind all eight failures is explained. This is an off-by-one error, the most common kind in loops. Evidences criterion 5.
(a) On the unsorted list with target 12: pass 1, low 0, high 6, mid 3, list[3] = 7, and 7 < 12 so low ← 4. Pass 2, low 4, high 6, mid 5, list[5] = 19, and 19 > 12 so high ← 4. Pass 3, low 4, high 4, mid 4, list[4] = 41, and 41 > 12 so high ← 3. Now low 4 > high 3, so it returns −1 — but 12 is at index 1. On pass 1 the algorithm threw away the left half because 7 was smaller than 12, which is only a safe decision if everything to the left of 7 is smaller still. In an unsorted list it is not, so the half it discarded contained the answer.
(b) First, when the data is not sorted and is only searched once or twice: sorting a million items takes far more work than one linear search through them, so sorting first would be slower overall. Second, when the list is small, say ten names in a class group: the difference is a handful of comparisons and linear search is simpler to write and harder to get wrong — Step 5 showed how easily binary search goes wrong. A third: when the data can only be read in order from the start, such as a stream of readings arriving from a sensor, you cannot jump to the middle.
The explanation of "sorted" comes straight from the trace, naming the pass where the wrong half was discarded, and both situations for linear search carry a reason, including the cost of sorting. Evidences criteria 3 and 4.