Loading…
Free A-Level Computer Science guide
Follow each comparison, update the right values and explain why the algorithm stops. These original examples support the AS recap topics in the October A-Level workshop and later A-Level revision.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
Linear search checks items one at a time until it finds a match or reaches the end. The values can be unsorted.
Binary search compares the target with the middle item of a sorted search range, then keeps only the half that could contain it.
Bubble sort repeatedly compares adjacent items and swaps them if they are in the wrong order. In an ascending, left-to-right pass, the largest remaining value reaches the end of the unsorted section.
You should be able to read a list index, an if condition and a loop. Revisit Python lists and functions if needed. Our Python examples use indices starting at 0 and return -1 when a search fails.
Search for 25 in [17, 3, 25, 8, 12]. Compare 17, then 3, then 25. The third comparison finds the target at index 2; the remaining items are not checked.
| Index | Value | Matches 25? |
|---|---|---|
| 0 | 17 | No |
| 1 | 3 | No |
| 2 | 25 | Yes — stop |
def linear_search(values, target):
for index in range(len(values)):
if values[index] == target:
return index
return -1
print(linear_search([17, 3, 25, 8, 12], 25)) # 2
print(linear_search([17, 3, 25, 8, 12], 9)) # -1The return -1 is outside the loop: it runs only after every item has failed to match. On an empty list, the loop runs zero times and the result is also -1.
For ascending values, low and high are inclusive index bounds. Calculate mid = (low + high) // 2, using integer division. A target larger than the middle value must lie to its right; a smaller target must lie to its left.
def binary_search(values, target):
# Precondition: values are sorted in ascending order.
low = 0
high = len(values) - 1
while low <= high:
mid = (low + high) // 2
if values[mid] == target:
return mid
if values[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
numbers = [3, 8, 12, 17, 25, 31, 40]
print(binary_search(numbers, 25)) # 4
print(binary_search(numbers, 9)) # -1Use mid + 1 or mid - 1 because the middle item has already failed to match. When low > high, there are no candidate items left. The condition low <= high lets the algorithm check a final one-item range.
Worked example
In [3, 8, 12, 17, 25, 31, 40], the first middle index is 3, holding 17. Since 25 is larger, set low = 4. The next middle index is 5, holding 31; set high = 4. The final middle index is 4, holding 25: return 4.
Count the middle items inspected: 17, 31, 25. That is three iterations. A question may count individual equality and ordering tests differently, so use its stated definition of a comparison.
| Iteration | low | high | mid | Value | Next step |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 17 | low = 4 |
| 2 | 4 | 6 | 5 | 31 | high = 4 |
| 3 | 4 | 4 | 4 | 25 | Return 4 |
For ascending order, swap a pair only when the left value is greater than the right value. A pass is one sweep through the current unsorted section; it can contain several comparisons and swaps.
| Pair compared | Action | List after comparison |
|---|---|---|
| 5 and 1 | Swap | [1, 5, 4, 2] |
| 5 and 4 | Swap | [1, 4, 5, 2] |
| 5 and 2 | Swap | [1, 4, 2, 5] |
def bubble_sort(values):
# Sort this list in place; the function returns no result.
for end in range(len(values) - 1, 0, -1):
swapped = False
for index in range(end):
if values[index] > values[index + 1]:
values[index], values[index + 1] = (
values[index + 1], values[index]
)
swapped = True
if not swapped:
break
numbers = [5, 1, 4, 2]
bubble_sort(numbers)
print(numbers) # [1, 2, 4, 5]After pass 1, 5 is in its final position. Pass 2 gives [1, 2, 4, 5]. Pass 3 compares 1 and 2, makes no swaps and stops. Each pass resets swapped; otherwise an earlier swap would prevent the early stop.
This function changes the supplied list in place. Call it, then print the list; assigning numbers = bubble_sort(numbers) would replace your variable with its implicit return value, None.
| Algorithm | Best case | Worst case | Requirement |
|---|---|---|---|
| Linear search | O(1) | O(n) | Can be unsorted |
| Binary search | O(1) | O(log n) | Sorted; direct indexed access |
| This bubble sort | O(n) | O(n²) | Comparable values |
This is an A-Level extension to the traces. Binary search halves its remaining range; linear search may visit every item. Bubble sort with this early-stop check makes one pass on already sorted data. Its worst case still needs roughly n(n − 1) / 2 adjacent comparisons. A version without early stopping has different best-case behaviour.
Use the algorithms on this page and zero-based indices. These four original questions total 11 marks, with indicative marking guidance.
Trace linear_search([14, 5, 22, 9, 18, 3], 9). State the values inspected, the return value and why no later item is inspected.
Indicative answer: It compares 14, 5, 22 and 9 in that order (1), returns index 3 (1), and stops because the item matches the target (1).
Use the binary-search algorithm above to find 15 in [4, 9, 15, 21, 28, 35, 43]. For each iteration, state the midpoint index and value, followed by the bound update or returned index.
Indicative answer: Award one mark for each correctly traced iteration:
mid = 3, value 21, so set high = 2 (1).mid = 1, value 9, so set low = 2 (1).mid = 2, value 15, so return index 2 (1).Each iteration's mark requires its midpoint index, value and correct bound update or return. Indices and values do not earn separate marks.
Give the list after one complete left-to-right bubble-sort pass on [7, 3, 6, 1]. Explain why it is still unsorted.
Indicative answer: The list after the complete pass is [3, 6, 1, 7] (1). It is still unsorted because 6 comes before the smaller value 1; another pass is needed (1).
To follow the swaps: comparing 7 and 3 gives [3, 7, 6, 1]; comparing 7 and 6 gives [3, 6, 7, 1]; comparing 7 and 1 gives [3, 6, 1, 7]. These intermediate states explain the result and carry no additional marks.
A learner applies binary search directly to [17, 3, 25, 8, 12]. Explain why this is unreliable and give a valid approach.
Indicative answer: The list is unsorted (1). Discarding a half on the basis of its middle value could discard the target (1). Use linear search, or sort the data before applying binary search (1).
OCR AS H046/02, Algorithms and problem solving, includes bubble sort, binary search and linear search in §2.3.1(b–d). OCR A-Level H446/02 develops algorithm knowledge further. This guide covers the three October recap topics, rather than every sorting algorithm or Paper 2 requirement. Other boards may use a different paper number and pseudocode conventions.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.