OCR GCSE Computer Science June 2024 Paper 2, Question 3(c): showing a binary search
OCR J277/02 June 2024, Question 3(c): show how a binary search finds 10 in the list 1 2 5 6 7 10 20, state its pre-requisite and name the sort that splits and recombines. The three marks explained, with the search to run.
Question 3(c) of the OCR GCSE Computer Science Paper 2 sat on 21 May 2024 (J277/02) asks you to show a binary search on seven numbers (3 marks), then state what a binary search needs (1 mark) and name a sorting algorithm from its description (1 mark). "Show" means use the numbers you are given. A general description gets one mark of the three.
We do not copy the exam paper here. Open it beside this page: OCR June 2024 J277/02 question paper (PDF). When you have finished, check the mark scheme too.
Part (i): find 10 in 1, 2, 5, 6, 7, 10, 20
Step 1. Pick the middle value. There are seven items, so the middle is the fourth: 6. Compare it with 10.
Step 2. Discard the half it cannot be in. 6 is less than 10, so 10 must be to the right. Discard 1, 2, 5 and 6. What is left is 7, 10, 20.
Step 3. Pick the middle again. The middle of 7, 10, 20 is 10. It matches. Found.
That is the whole answer, and each step is a mark. Write it as three short lines, or draw the list three times with the discarded part crossed out.
Part (ii): the pre-requisite
The data must be sorted (in order). Without that, "it must be to the right" would not be true.
Part (iii): which sort splits and recombines?
Merge sort. It splits the list down to individual items, then merges them back together in order. A bubble sort swaps neighbours. An insertion sort moves each item into place in a sorted section.
Where the marks are lost
- No numbers. "Find the middle, discard half, repeat" is a description, not a demonstration. Only the first mark can be given for a generic answer.
- Discarding the wrong things. If you list what goes, it must be 1, 2, 5 and 6. The middle value has been checked, so it goes too.
- Carrying on after it is found. Once the middle value is 10 the search is over.
- Checking the items one by one. That is a linear search, and it gets nothing here.
Run it
A binary search in Python that prints each step in words. Change TARGET, and trace it on paper before you run it.
The program
from bugbot import *
connect()
# change TARGET and press Run
TARGET = 10
data = [1, 2, 5, 6, 7, 10, 20]
low = 0
high = len(data) - 1
found = False
while low <= high and not found:
mid = (low + high) // 2
print("looking at", data[low:high + 1], "middle is", data[mid])
if data[mid] == TARGET:
found = True
elif data[mid] < TARGET:
print(" ", data[mid], "is less than", TARGET, "so discard the left side")
low = mid + 1
else:
print(" ", data[mid], "is more than", TARGET, "so discard the right side")
high = mid - 1
if found:
led("green")
print("found", TARGET)
else:
led("red")
print(TARGET, "is not in the list")
Want to watch a robot do this along a row of cards? It is in the guide: Linear search and binary search explained.
Questions
What is the answer to OCR J277 June 2024 Paper 2 Question 3(c)(i)?
Compare 10 with the middle value, 6. 6 is less than 10, so discard the left side (1, 2, 5 and 6). The middle of what is left (7, 10, 20) is 10, so it is found.
What is the pre-requisite for a binary search?
The data must be sorted into order before the search starts.
What happens in a binary search if there are two middle values?
With an even number of items there is no single middle. Choose either the left or the right of the two middle items, and be consistent. Programs usually take the left one, because integer division rounds down.
More from this paper
- Question 2: Complete a flowchart that decides odd or even with MOD 4 marks
- Question 3(a), (b): Define a syntax error, then correct two logic errors in a range check 6 marks
- Question 5: A truth table for (A AND B) OR C and a circuit for NOT A AND (B OR C) 7 marks
- Question 6: String methods: upper, left, right with a cast, and concatenation 6 marks
- Question 8: Maintainability, and a function that moves a character and keeps it in range 10 marks
Every OCR J277 question we have worked · Guide: Big O notation explained
Learn it step by step
- F5.6 Binary search Algorithms
- F5.9 Merge sort and comparing algorithms Algorithms
This is our own explanation of a published exam question. It is not written or endorsed by OCR, and the question paper and mark scheme remain OCR's copyright. Read them on OCR's site with the links on this page.