A-LevelComputer ScienceAlgorithm design and problem-solving9618/31 · May/June 2024 · Q108 Marks

State a condition that must be true for an array to be searchable for a binary search.

(a)State a condition that must be true for an array to be searchable for a binary search.[1]
(b)Complete the given pseudocode to find an item in a 1D array Names of type STRING using a binary search. DECLARE Names : ARRAY[1:100000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE CurrentItem : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList ← 1 EndOfList ← 100000 OUTPUT "Which name do you wish to find?" INPUT ToFind NotInList ← FALSE WHILE .................. AND ................... CurrentItem ← (TopOfList + EndOfList) DIV 2 IF .......................... THEN Found ← TRUE ELSE IF TopOfList >= EndOfList THEN .......................... ELSE IF ToFind > Names[CurrentItem] THEN .......................... ELSE .......................... ENDIF ENDIF ENDIF ENDWHILE IF Found = TRUE THEN OUTPUT "Item found at position ", CurrentItem, " in array" ELSE OUTPUT "Item not in array" ENDIF[5]
(c)Describe the performance of a binary search in relation to the number of data items in the array being searched. Refer to Big O notation in your answer.[2]

Mark scheme

Marking points from the official mark scheme (May/June 2024). The mark or mark type is shown in brackets.

[1] 10(a) One mark
10(a) The elements are sorted according to the compare function / in ascending / descending order.
[5] 10(b) One mark for each correctly completed line (Max 5)
10(b) WHILE Found = FALSE AND NotInList = FALSE
10(b) IF ToFind = Names[CurrentItem]// Names[CurrentItem] = ToFind THEN
10(b) NotInList ← TRUE
10(b) TopOfList ← CurrentItem + 1
10(b) EndOfList ← CurrentItem - 1
[2] 10(c) One mark from
10(c) MP1 Big O for a binary search is O(Log2 n).
10(c) MP2 Big O notation is used to indicate the time/space complexity of an algorithm.
10(c) One mark from
10(c) MP3 The time taken to complete the search increases logarithmically as the number of search items increases linearly
10(c) MP4 The time taken to complete the search increases linearly as the number of search items increases exponentially
10(c) MP5 As the search field is repeatedly getting smaller, the number of comparisons made before the item is found, or the number of items runs out, is relatively small.

On Oracle Prep you can write or photograph your own answer and have it marked by AI against this mark scheme, with feedback on what you missed.