A-LevelComputer ScienceAlgorithm design and problem-solving9618/31 · Oct/Nov 2022 · Q129 Marks

The array Names [0:99] is in alphabetical order. Complete this pseudocode binary search algorithm. Lower ← 0 Mid ← 0 Exit ← FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT OUTPUT Target, " does not exist" Exit ← TRUE ENDIF Mid ← Lower + (Upper – Lower + 1) DIV 2 IF Names [Mid] < Target THEN ENDIF IF Names [Mid] > Target THEN ENDIF OUTPUT Target, " was found at location ", Mid Exit ← TRUE ENDIF

(a)The array Names [0:99] is in alphabetical order. Complete this pseudocode binary search algorithm. Lower ← 0 Mid ← 0 Exit ← FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT OUTPUT Target, " does not exist" Exit ← TRUE ENDIF Mid ← Lower + (Upper – Lower + 1) DIV 2 IF Names [Mid] < Target THEN ENDIF IF Names [Mid] > Target THEN ENDIF OUTPUT Target, " was found at location ", Mid Exit ← TRUE ENDIF[6]
(b)(i)Big O notation is used to classify efficiency of algorithms. The Big O notation for time complexity in a binary search is O(log n). State the Big O notation for time complexity of a linear search.[1]
(b)(ii)Describe the meaning of O(log n) as it applies to a binary search algorithm.[2]

Mark scheme

Marking points from the official mark scheme (Oct/Nov 2022). The mark or mark type is shown in brackets.

[6] One mark for each point (Max 6)
• Initialisation of upper bound
• Test if upper bound is less than lower bound
• Re-setting of mid value if current value is lower than the target
• Re-setting of mid value if current value is higher than the target
• Finding the value
• Correct termination of loop
Lower ← 0 Upper ← 99 Mid ← 0 Exit ← FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit ← TRUE ENDIF Mid ← Lower + (Upper – Lower + 1) DIV 2 IF Names [Mid] < Target THEN Lower ← Mid + 1 ENDIF IF Names [Mid] > Target THEN Upper ← Mid - 1 ENDIF IF Names [Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit ← TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE
[1] O(n)
[2] One mark for each point (Max 2)
• O(log n) is a time complexity that uses logarithmic time.
• The time taken goes up linearly as the number of items rises exponentially
• O(log n) is the worst case scenario (time complexity for a binary search).

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.