Searching algorithms: linear and binary search – GCSE Computer Science exam questions with mark scheme

1Grade 1–33 marks

(a) State one requirement that the data must meet before a binary search can be used. [1]

(b) Give one advantage of a linear search over a binary search. [1]

(c) A linear search is carried out on an unsorted list of 1000 items. State the maximum number of items that may need to be checked. [1]

(a) The data must be sorted / in order(1)
(b) e.g. works on unsorted data / simpler to code / can be quicker for very small lists or when the item is near the start(1)
(c) 1000(1)
Answer: (a) Sorted; (b) works on unsorted data; (c) 1000
Examiner tip: In (b), 'it is faster' doesn't get the mark. Linear search is usually slower, so the advantage you give must be correct.

2Grade 4–53 marks

A list of numbers is shown.

[3, 8, 12, 19, 25, 34, 41, 47, 50]

Show the stages of a binary search to find the number 34. [3]

Compares 34 with the middle item 25. 34 is greater, so the left half (and 25) is discarded(1)
Compares 34 with the middle of the remaining list [34, 41, 47, 50], 41. 34 is smaller, so 41 and the items to its right are discarded. Accept 47 as the middle if the candidate is consistent(1)
Continues halving until 34 is compared with itself: 34 is found (stop). (With 41 as the second middle, the remaining item is 34.)(1)
Answer: 25 → discard left; 41 → discard right; 34 found
Examiner tip: You must say which half is discarded each time. Just listing the middle values only shows part of the method.

3Grade 6–75 marks

Write a function called linearSearch that:

• takes an array items and a value target as parameters

• returns the index of the first position where target is found

• returns -1 if target is not in the array.

Do not use a built-in search function.

Use OCR Exam Reference Language or a high-level programming language. [5]

Function defined with the name linearSearch and two parameters (items, target), and closed (endfunction / correct indentation)(1)
Loop that can visit every index of the array, e.g. for i = 0 to items.length - 1; allow a while loop with a counter that stops at the end of the array; allow len(items) in Python(1)
Compares items[i] with target(1)
Returns i (the index) when target is found and stops searching; allow: stores the index / sets a found flag, exits the loop and returns the stored index; allow any method that keeps the first matching index (e.g. only stores i if nothing has been stored yet); do not award if the code would return the index of a later match(1)
Returns -1 only after every item has been checked without finding target (not inside the loop as an else); allow: a result variable initialised to -1 before the loop and returned after it(1)

Examiner tip: Don't put 'else return -1' inside the loop. That stops the search after checking only the first item.

Book a free introductory session and we'll find exactly which step is costing you.