ExpertMedium4 marksStructured
AQA GCSE · Question 12.1 · Fundamentals of algorithms
Figure 11 shows a binary search algorithm that has been programmed in Python.
Figure 11
python
animals = ["cat", "dog", "hippo", "llama", "ox", "rat", "tiger", "wolf"]
animalToFind = input("What animal would you like to find? ")
validAnimal = False
start = 0
finish = len(animals) - 1
while validAnimal == False and start <= finish:
mid = (start + finish) // 2
if animals[mid] == animalToFind:
validAnimal = True
elif animalToFind > animals[mid]:
start = mid + 1
else:
finish = mid - 1
print(validAnimal)
Complete the trace table for the program in Figure 11 if the user input is wolf. Part of the table has already been filled in.
Figure 11 shows a binary search algorithm that has been programmed in Python.
Figure 11
python
animals = ["cat", "dog", "hippo", "llama", "ox", "rat", "tiger", "wolf"]
animalToFind = input("What animal would you like to find? ")
validAnimal = False
start = 0
finish = len(animals) - 1
while validAnimal == False and start <= finish:
mid = (start + finish) // 2
if animals[mid] == animalToFind:
validAnimal = True
elif animalToFind > animals[mid]:
start = mid + 1
else:
finish = mid - 1
print(validAnimal)
Complete the trace table for the program in Figure 11 if the user input is wolf. Part of the table has already been filled in.
How to approach this question
Trace the `while` loop, updating the `start`, `finish`, and `mid` variables in each iteration.
- **Initial State (given):** `animalToFind`="wolf", `validAnimal`=False, `start`=0, `finish`=7.
- **Loop 1:**
- `mid` = (0 + 7) // 2 = 3.
- `animals[3]` is "llama".
- `animalToFind` ("wolf") > "llama", so `start` becomes `mid + 1` = 4.
- *Table Row 2: validAnimal=False, start=4, finish=7*
- **Loop 2:**
- `mid` = (4 + 7) // 2 = 5.
- `animals[5]` is "rat".
- `animalToFind` ("wolf") > "rat", so `start` becomes `mid + 1` = 6.
- *Table Row 3: validAnimal=False, start=6, finish=7*
- **Loop 3:**
- `mid` = (6 + 7) // 2 = 6.
- `animals[6]` is "tiger".
- `animalToFind` ("wolf") > "tiger", so `start` becomes `mid + 1` = 7.
- *Table Row 4: validAnimal=False, start=7, finish=7*
- **Loop 4:**
- `mid` = (7 + 7) // 2 = 7.
- `animals[7]` is "wolf".
- `animals[mid] == animalToFind` is true. `validAnimal` becomes `True`.
- *Table Row 5: validAnimal=True, start=7, finish=7*
- The `while` loop condition `validAnimal == False` is now false, so the loop terminates.
Full Answer
The completed trace table is:
- Row 1: animalToFind="wolf", validAnimal=False, start=0, finish=7, mid=3
- Row 2: animalToFind="wolf", validAnimal=False, start=4, finish=7, mid=5
- Row 3: animalToFind="wolf", validAnimal=False, start=6, finish=7, mid=6
- Row 4: animalToFind="wolf", validAnimal=False, start=7, finish=7, mid=7
- Row 5: animalToFind="wolf", validAnimal=True, start=7, finish=7, mid=7
A binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
**Trace:**
- **List:** `["cat", "dog", "hippo", "llama", "ox", "rat", "tiger", "wolf"]` (indices 0-7)
- **Target:** "wolf"
- **Pass 1:** `start=0`, `finish=7`. `mid=(0+7)//2=3`. `animals[3]` is "llama". Since "wolf" comes after "llama" alphabetically, we know the target must be in the upper half. We update `start` to `mid+1`, so `start` becomes 4.
- **Pass 2:** `start=4`, `finish=7`. `mid=(4+7)//2=5`. `animals[5]` is "rat". "wolf" > "rat", so we update `start` to `mid+1`, making `start` 6.
- **Pass 3:** `start=6`, `finish=7`. `mid=(6+7)//2=6`. `animals[6]` is "tiger". "wolf" > "tiger", so we update `start` to `mid+1`, making `start` 7.
- **Pass 4:** `start=7`, `finish=7`. `mid=(7+7)//2=7`. `animals[7]` is "wolf". We have found the item. `validAnimal` is set to `True`. The loop terminates.
Common mistakes
✗ Incorrectly calculating the `mid` point, especially with integer division.\n✗ Updating the wrong variable (`start` instead of `finish` or vice-versa).\n✗ Forgetting to add 1 or subtract 1 when updating `start` or `finish`.
Practice the full AQA GCSE Computer Science Paper 1 Python
31 questions · hints · full answers · grading
More questions from this exam
Q01.1Figure 1 shows an algorithm, represented using pseudo-code, which assigns a different value to fo...EasyQ01.2The variable `x` is assigned a value using the statement:
`x ← LEN(state)`
Using Figure 1, what ...EasyQ01.3What is the result of concatenating the contents of the variables `city` and `landmark` in Figure 1?EasyQ01.5The subroutine `POSITION` finds the first position of a character in a string.
For example, `POSI...EasyQ02.1Figure 2 shows an algorithm that uses integer division which has been represented using pseudo-co...Easy