Complete the pseudocode to find an item in a 1D array Widgets of type STRING, using a linear search. DECLARE Widgets : ARRAY[1:50000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE Count : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList ← 1 EndOfList ← 50000 OUTPUT "Enter the name of the item you wish to find " INPUT ToFind NotInList ← FALSE Count ← TopOfList WHILE IF Found← TRUE ENDIF Count← Count + 1 IF AND NotInList ← TRUE ENDIF ENDWHILE IF Found = TRUE THEN OUTPUT "Item found at position ", Count – 1, " in array" ELSE OUTPUT "Item not in array" ENDIF

Mark scheme

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

1. [4] One mark for each correctly completed line (Max 4)
2. [4] WHILE Found = FALSE AND NotInList = FALSE // Count <= EndOfList
3. [4] IF ToFind = Widgets [Count] // Widgets[Count] = ToFind THEN
4. [4] Found ← TRUE
5. [4] IF Found = FALSE AND Count > EndOfList THEN
6. [4] NotInList ← TRUE
7. [4] One mark per mark point (Max 3)
8. [4] MP1 Linear search sequentially checks each element of the array / list.
9. [4] MP2 ... until the matching element is found, or the end of the array / list is reached.
10. [4] MP3 Binary search finds the mid-point of an array/list and determines which side contains the item to be found
11. [4] MP4 ... it discards the half of the array/list not containing the search item // it finds the position of a target value within an array / list by repeatedly halving the target search field.
12. [4] MP5 The binary search requires the elements to be sorted // The linear search does not require the elements to be sorted.
13. [4] MP6 The binary search will usually do many fewer comparisons of records/iterations against the target than a linear search before it finds its target.
14. [4] MP7 Linear search starts at the beginning of the array/list and binary search starts in the middle of the array/list.
15. [4] One mark per mark point (Max 2)
16. [4] MP8 Big O for binary search is O (Log2 n)
17. [4] MP9 Big O for linear search is O (n)
18. [4] MP10 Big O notation is used to indicate the time / space complexity of an algorithm