OCR GCSE Computer Science June 2022 Paper 2, Question 3(b) and (c): describing the two searches

OCR J277/02 June 2022, Question 3(b) and (c): describe the steps of a binary search for 4 marks and of a linear search for a number that is not in the list for 2. What the mark scheme wants in each step, with both searches to run and compare.

Past paper questionOCR J277/02June 2022 Paper 26 marksExplain

Questions 3(b) and 3(c) of the OCR GCSE Computer Science Paper 2 sat on 27 May 2022 (J277/02) are "describe the steps" questions: 4 marks for a binary search, and 2 for a linear search that does not find its number. There is no code to write. The marks go to precise wording, and vague wording that feels right is refused.

We do not copy the exam paper here. Open it beside this page: OCR June 2022 J277/02 question paper (PDF). When you have finished, check the mark scheme too.

Part (b): the steps of a binary search (4 marks)

Any four of these:

1. Pick the middle item of the list. (With an even number of items, the one to the left or right of the middle.)
2. Check whether it equals the number you are looking for. If so, stop: it is found.
3. If the number you want is larger, discard the left half. If it is smaller, discard the right half.
4. Repeat with the half that is left...
5. ...until the number is found, or the remaining list has no items left, which means it is not there.

Where the marks are lost in part (b)

• "Split the list in half." On its own this is refused as a first step. The search does not split anything. It picks the middle item and compares.
• "Compare the middle number." Compare it with what, and to find out what? Say that you check whether it matches the target.
• "Repeat until the number is not in the list." How would the search know? Say that it stops when there is nothing left to search.
• Forgetting the direction. "Discard half" is not enough. Say which half, and why.

Part (c): a linear search for a number that is not there (2 marks)

1. Start with the first value.
2. Check every value in order to the end of the list.

The number is not in the list, so the search never stops early. It has to look at all eight values before it can say so.

Where the marks are lost in part (c)

• "Repeat until the value is found." The question says it is not in the list.
• "Checks each value", "one by one". These do not say in order. "Checks each value from the beginning to the end" says both things and gets both marks.

Run it

Both searches on the sorted list from part (a), counting comparisons. 50 is not in the list, so this is part (c) exactly: the linear search needs all 8 comparisons and the binary search needs 4. The robot drives 5 cm for every comparison the linear search made.

from bugbot import *
connect()

# change TARGET and press Run
TARGET = 50

data = [-99, -27, -13, 0, 12, 17, 45, 100]

checks = 0
found = False
for value in data:
    checks = checks + 1
    if value == TARGET:
        found = True
        break
print("linear search:", found, "after", checks, "comparisons")
linear = checks

checks = 0
found = False
low = 0
high = len(data) - 1
while low <= high and not found:
    mid = (low + high) // 2
    checks = checks + 1
    print("  middle item is", data[mid])
    if data[mid] == TARGET:
        found = True
    elif TARGET > data[mid]:
        low = mid + 1
    else:
        high = mid - 1
print("binary search:", found, "after", checks, "comparisons")
forward(60, distance=linear * 5)

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

Questions

How do you describe a binary search for 4 marks?

Pick the middle item and check whether it matches the target. If the target is larger, discard the left half, and if it is smaller, discard the right half. Repeat with the remaining half until the item is found or no items are left.

How do you describe a linear search?

Start at the first item and check each item in order until the target is found or the end of the list is reached.

Which is faster, a linear search or a binary search?

A binary search is much faster on a large sorted list, because each comparison discards half of what is left. A linear search can still be quicker when the item is near the front, and it is the only choice when the list is not sorted.

More from this paper

• Question 3(a): Show each step of a merge sort on eight numbers 3 marks

Every OCR J277 question we have worked · Guide: Linear search and binary search explained

Learn it step by step

1. F5.6 Binary search Algorithms
2. F5.5 Linear search 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.