Question bank › GCSE Computer Science › Fundamentals of algorithms

Searching algorithms: linear & binary search

Answer on paper first, then reveal the mark scheme one mark at a time.

1Grade 4–54 marks

A binary search is used to find the value 63 in this sorted list:

[4, 9, 15, 22, 28, 33, 41, 50, 56, 63, 70]

(a) List, in order, each value that is compared with 63 during the search. [3]

(b) Explain why a binary search could not be used on the list [22, 4, 70, 9, 41]. [1]

(a) 33 (first value compared)(1)
(a) 56(1)
(a) 63 (and the search stops). Allow 33, 56, 70, 63 if the upper middle item is chosen consistently when there is an even number of items; max 2 marks if extra/incorrect values appear(1)
(b) The list is not sorted / not in order (binary search needs ordered data to know which half to discard)(1)
Answer: (a) 33, 56, 63 (b) the list is not sorted
Examiner tip: Write down only the items actually compared, in order. Listing the halves of the list instead of the middle values loses marks.

2Grade 8–96 marks

An array names holds a list of student names. Write an algorithm, using either pseudo-code or program code in the language you are studying (C#, Python or VB.NET), that:

asks the user to enter a name to search for
uses a linear search to find the first position of that name in names
outputs the index of the name if it is found, or outputs −1 if it is not in the array
stops searching as soon as the name is found.

[6]

Gets the name to search for from the user (e.g. target ← USERINPUT / input()). Minor syntax errors are not penalised(1)
Uses a loop that can go through every element of the array (e.g. index from 0 up to LEN(names) − 1)(1)
Compares the current element names[i] with the target(1)
Outputs the index of the element when a match is found(1)
Loop stops when the item is found (e.g. found flag / WHILE condition / RETURN) — no further items are checked(1)
Outputs −1 only if the whole array has been checked without finding the name (i.e. not output for every non-matching item)(1)

Answer: e.g.

target ← USERINPUT
i ← 0
found ← False
WHILE i < LEN(names) AND found = False
   IF names[i] = target THEN
      found ← True
   ELSE
      i ← i + 1
   ENDIF
ENDWHILE
IF found = True THEN
   OUTPUT i
ELSE
   OUTPUT -1
ENDIF

Examiner tip: The most common lost mark is outputting −1 inside the loop each time an item doesn't match. Only decide 'not found' after the loop ends.

Still losing marks on this topic?

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

Book a free intro