AQA GCSE Computer Science June 2023 Paper 1, Question 12.1: the binary search trace table

AQA 8525 June 2023 Paper 1, Question 12.1: trace a binary search written in Python as it looks for wolf in a list of eight animals. Every pass worked through, the four marks explained, and the search to run and change.

Past paper questionAQA 8525/1BJune 2023 Paper 14 marksTrace table

Question 12.1 of the AQA GCSE Computer Science Paper 1 sat on 19 May 2023 (8525/1B, the Python paper) shows a binary search written in Python and asks you to trace it when the user types wolf. It is worth 4 marks. The first row of the table is filled in for you.

We do not copy the exam paper here. Open it beside this page: AQA June 2023 Paper 1B question paper (PDF). When you have finished, check the mark scheme too.

The question in short

The list holds eight animals in alphabetical order. Their index numbers matter, so write them above the list on the paper before you start:

The program keeps a start and a finish. While the animal has not been found and start has not passed finish, it:

• works out mid as (start + finish) // 2;
• if the animal at mid is the one wanted, sets validAnimal to True;
• if the animal wanted comes later in the alphabet, moves start to mid + 1;
• otherwise moves finish to mid - 1.

The columns are animalToFind, validAnimal, start, finish and mid. The given first row is wolf, False, 0, 7, 3.

Work it through

Pass 1 (given). mid is (0 + 7) // 2 = 3. The animal at 3 is llama. Wolf comes after llama, so start becomes 3 + 1 = 4.

Pass 2. mid is (4 + 7) // 2. That is 11 // 2, which is 5, because // throws the half away. The animal at 5 is rat. Wolf comes after rat, so start becomes 6.

Pass 3. mid is (6 + 7) // 2 = 13 // 2 = 6. The animal at 6 is tiger. Wolf comes after tiger, so start becomes 7.

Pass 4. mid is (7 + 7) // 2 = 7. The animal at 7 is wolf. Found: validAnimal becomes True and the loop ends.

The finished trace table

finish never changes, because wolf is always in the upper half. animalToFind never changes at all.

Where the four marks are

• One mark for the animalToFind, validAnimal and finish columns, with nothing extra in them.
• One mark for the start column: 0, 4, 6, 7.
• One mark for 5 as the second value of mid.
• One mark for the rest of mid: 6, then 7.

Any error caps you at 3. Values can sit on different rows so long as the order down each column is clear.

Where the marks are lost

• Rounding 5.5 up. (4 + 7) // 2 is 5, not 6. Integer division always rounds down. The mark scheme gives a whole mark to this one number.
• Writing new values in finish. It stays at 7. Copying 7 down the column is ignored, but writing 6 or 5 there loses the mark.
• Forgetting True. The last thing that happens is validAnimal changing. It belongs in the table.
• Comparing words by length. "wolf" > "llama" compares alphabetically, letter by letter. W comes after L, so it is True.

Run it

The same search, printing a row of the trace table on every pass. Change TARGET and predict the rows before you run it.

from bugbot import *
connect()

# change TARGET and press Run
TARGET = "wolf"

animals = ["cat", "dog", "hippo", "llama", "ox", "rat", "tiger", "wolf"]
valid_animal = False
start = 0
finish = len(animals) - 1
print("start finish mid  animal there")
while valid_animal == False and start <= finish:
    mid = (start + finish) // 2
    print(start, finish, mid, animals[mid])
    if animals[mid] == TARGET:
        valid_animal = True
    elif TARGET > animals[mid]:
        start = mid + 1
    else:
        finish = mid - 1
print(valid_animal)

Want to watch a robot do a binary search along a row of cards? It is in the guide: Linear search and binary search explained.

Now change it

Set TARGET to "zebra". It is not in the list. Trace it first: what are the last values of start and finish, and why does the loop stop?

Questions

What is the answer to AQA GCSE Computer Science 2023 Paper 1 Question 12.1?

The start column is 0, 4, 6, 7. The finish column stays at 7. The mid column is 3, 5, 6, 7. validAnimal is False and becomes True on the last pass, when mid is 7 and the animal there is wolf.

How do you work out the midpoint in a binary search?

Add the start and finish index numbers and do an integer division by 2. With start 4 and finish 7 the midpoint is 11 // 2 = 5. Integer division rounds down.

Why does a binary search need a sorted list?

Each comparison throws away the half of the list that the target cannot be in. That only works if everything before the midpoint is smaller and everything after it is bigger, which means the list must be in order.

More from this paper

• Question 4: Trace a Python function with three sets of inputs, then make it robust 4 marks
• Question 5: Trace a flowchart with a loop 3 marks
• Question 10: Trace nested FOR loops over a list of scores and find the error 6 marks

Every AQA 8525 question we have worked · Guide: Linear search and binary search explained

Learn it step by step

1. F5.6 Binary search Algorithms
2. F13.2 Trace tables Exam preparation

This is our own explanation of a published exam question. It is not written or endorsed by AQA, and the question paper and mark scheme remain AQA's copyright. Read them on AQA's site with the links on this page.