A-LevelComputer ScienceAlgorithm design and problem-solving9618/32 · May/June 2022 · Q813 Marks
A binary search or a linear search can be used to look for a specific value in an array.
- (a)Complete this pseudocode algorithm for a linear search. DECLARE MyList : ARRAY[0:9] OF INTEGER DECLARE MaxIndex : INTEGER DECLARE Index : INTEGER DECLARE Found : BOOLEAN DECLARE ValueToFind : INPUT ValueToFind Found ← FALSE Index ← 0 MaxIndex ← REPEAT IF MyList[Index] = ValueToFind THEN Found ← TRUE ENDIF Index ← UNTIL Found OR Index > MaxIndex IF Found THEN OUTPUT "Value found at position ", Index ELSE OUTPUT ENDIF[4]
- (b)(i)State the necessary condition for a binary search.[1]
- (b)(ii)Describe how to perform a binary search.[4]
- (b)(iii)Explain how the performance of a binary search varies according to the number of values in the array.[1]
- (c)Compare the performance of the algorithms for a binary search and a linear search using Big O notation for order of time complexity.[3]
Mark scheme
Marking points from the official mark scheme (May/June 2022). The mark or mark type is shown in brackets.
- [4] INTEGER 9 // LENGTH (MyList) - 1 Index + 1 "Value not found" (or any similar phrase)
- [1] The list to be searched must be ordered/sorted
- [4] Any four from MP1 Find the middle item / index MP2 Check the value of middle item in the list to be searched MP3 If equal item searched for is found MP4 If this is not equal/greater/less than the item searched for MP5 discard the half of the list that does not contain the search item MP6 Repeat the above steps until the item searched for is found MP7 or there is only one item left in the list and it is not the item searched for // lower bound > / = upper bound
- [1] As the number of items in the list increases the time to search the list increases
- [3] MP1 Linear search O(n) and Binary search O(log2n) / O(Log n) MP2 time to search increases linearly in relation to the number of items in the list for a linear search and logarithmically for a Binary search MP3 time to search increases less rapidly for a binary search and time to search increases more rapidly for a linear search
Write your answer and get it marked
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.
Sign up free →