| Date | May 2022 | Marks available | 1 | Reference code | 22M.1.SL.TZ0.14 |
| Level | SL | Paper | 1 | Time zone | no time zone |
| Command term | Outline | Question number | 14 | Adapted from | N/A |
Question
The array DATA_ARR[] is a one-dimensional array of 12 integers.
Algorithm 1 represents a method of searching the array DATA_ARR[] to see if it contains a specific value.
Algorithm 1
input TO_FIND
LIMIT = 11
LOC = FALSE
ITERATE = 0
loop while not LOC and ITERATE <= LIMIT
if DATA_ARR[ITERATE] = TO_FIND then
LOC = TRUE
end if
ITERATE = ITERATE + 1
end loop
if LOC then
output TO_FIND, "is in the array"
else
output TO_FIND, "is NOT in the array"
end if
Algorithm 2 represents an alternative method of searching the array DATA_ARR[] to see if it contains a specific value.
Algorithm 2
input TO_FIND
LOC = FALSE
LOW_LIM = 0
UP_LIM = 11
loop while LOW_LIM <= UP_LIM and LOC = FALSE
MID_VAL = (LOW_LIM + UP_LIM) div 2
if DATA_ARR[MID_VAL] = TO_FIND then
LOC = TRUE
else
if TO_FIND < DATA_ARR[MID_VAL] then
UP_LIM = MID_VAL - 1
else
LOW_LIM = MID_VAL + 1
end if
end if
end loop
if LOC = TRUE then
output TO_FIND, "is in the array"
else
output TO_FIND, "is NOT in the array"
end if
Copy and complete the trace table for Algorithm 1 using TO_FIND = 39.
The first value of the first row has been done for you.
State the constant used in Algorithm 1.
Copy and complete the trace table for Algorithm 2 using TO_FIND = 50.
The first two values of the first row have been done for you.
Outline why MID_VAL could not be a constant.
Evaluate the use of a sequential search and a binary search including the advantages and disadvantages of each.
Markscheme
Award [4 max].
Award [1] for TO_FIND and LOC columns;
Award [1] for ITERATE column;
Award [1] for DATA_ARR[ITERATE] column;
Award [1] for the correct output;
Award [1 max].LIMIT
Award [4 max].
Award [1] for LOW_LIM column;
Award [1] for UP_LIM column;
Award [1] for MID_VAL and DATA_ARR[MID_VAL] columns;
Award [1] for TO_FIND, LOC and Output columns;
Award [1 max].
The value (of MID_VAL) changes during the operation of the algorithm;
Award [5 max].
Award [3 max] for sequential search
The algorithm searches through every element in the array starting at the beginning and working through one after the other;
…until the required item is found;
This method is potentially slow if the data set is large and the required element is towards the end of the list;
The data does not need to be in any particular order;
Award [3 max] for binary search
The data must be sorted before it is stored;
After comparing the data set with the target data, half of the data can be discounted using a simple condition;
…enabling the target to be more quickly located;
Note to examiners: Big O notation is not on the syllabus so answers with reference to this are not expected, however, if this type of answer is seen, please allow, for example:
Sequential: main disadvantage is O(N) so inefficient;
advantage is that it works with an unsorted array;
Binary search: main advantage is that it’s efficient as it’s O(log n);
disadvantage is that the array must be sorted (and so must be sortable – not all data has a defined sort order);
Binary search cannot be performed on a linked list but a sequential search can;
Examiners report
Candidates generally constructed the correct trace table for this question; however, marks were often lost by not providing the correct quantity of iterations for the trace, or by making errors in how the output would actually appear if the program ran.
The vast majority of candidates correctly identified LIMIT as the constant in the algorithm.
Candidates generally performed less well on the trace for the second algorithm (binary search), with similar errors to the trace carried out in part (a). Also, as this algorithm required more processing, additional errors included incorrect calculations of the variables, leading to incorrect values being displayed in the trace table.
The vast majority of candidates gave an appropriate reason why the variable MID_VAL could not be a constant in the given algorithm.
Virtually all candidates were able to evaluate the use of a sequential and a binary search, with many of these candidates achieving high or full marks. One point that was often missing form candidates’ responses, however, which is fundamental to the topic, was the need for the data to be sorted/ordered for a binary search to work.
