Searching algorithms (linear, binary, binary tree) – A-level Computer Science exam questions with mark scheme

1Core3 marks

The list below is sorted in ascending order, with indexes starting at 0.

[3, 8, 12, 17, 23, 29, 35, 41, 50]

A binary search uses mid = (low + high) DIV 2, starting with low = 0 and high = 8.

(a) Show the values of mid and the item examined at each step when searching for 12. [2]

(b) State why a binary search cannot be used on an unsorted list. [1]

(a) Step 1: mid = 4, item 23 examined (the comparison and new low/high values shown in brackets here are not required for the mark: 12 < 23 so high becomes 3)(1)
(a) Step 2: mid = 1, item 8 examined (12 > 8 so low becomes 2); step 3: mid = 2, item 12 examined and found – both mid values 1 and 2 (with items 8 and 12) needed for the mark; ignore extra working such as low/high values(1)
(b) The algorithm relies on the items being in order to decide which half of the list to discard at each step; in an unsorted list the item could be in the discarded half (allow: it could not tell whether the item is before or after the middle)(1)
Answer: (a) mid = 4 (23), mid = 1 (8), mid = 2 (12, found) (b) It relies on the ordering to discard half the list.
Examiner tip: Show every mid value and the item at it – examiners award the method marks for the sequence, not just the final index.

2Stretch7 marks

A sorted list Data is stored in an array with indexes starting at 0.

(a) Write a recursive subroutine BinarySearch(Data, target, low, high) that returns the index of target within Data[low..high], or −1 if it is not present. The middle index must be found using (low + high) DIV 2. You may write your answer in pseudo-code or a programming language you have studied. [4]

(b) The list contains 16 items. State the greatest number of items that need to be examined by the search in the worst case. [1]

(a) Base case: IF low > high THEN RETURN −1 (must be checked before Data[mid] is accessed)(1)
(a) mid ← (low + high) DIV 2 and Data[mid] compared with target; RETURN mid if they are equal(1)
(a) If target < Data[mid], RETURN BinarySearch(Data, target, low, mid − 1) – the result of the recursive call is returned (allow the tests in the other order, e.g. target > Data[mid] tested first, provided each branch searches the correct half)(1)
(a) Otherwise RETURN BinarySearch(Data, target, mid + 1, high) – the result of the recursive call is returned (do not award if mid rather than mid ± 1 is passed, as the search may never end)(1)
(b) 5(1)
(c) Each recursive call creates a new stack frame (parameters, return address, local variables) on the call stack(1)
(c) Up to about log₂ n frames exist at the same time, whereas an iterative version only needs a fixed number of variables (constant memory)(1)

Answer: (a)

SUBROUTINE BinarySearch(Data, target, low, high)
  IF low > high THEN
    RETURN -1
  ENDIF
  mid ← (low + high) DIV 2
  IF Data[mid] = target THEN
    RETURN mid
  ELSEIF target < Data[mid] THEN
    RETURN BinarySearch(Data, target, low, mid - 1)
  ELSE
    RETURN BinarySearch(Data, target, mid + 1, high)
  ENDIF
ENDSUBROUTINE

(b) 5 (c) Every call adds a stack frame, so memory use grows with the recursion depth (about log₂ n); the iterative version uses a fixed amount.

Examiner tip: In (a), write RETURN in front of each recursive call: without it the result of the inner call is thrown away and the subroutine returns nothing.

Stuck on this topic?