The following pseudocode performs a linear search on an array of names to find a target name. Some lines are missing. DECLARE Names : ARRAY[1:100] OF STRING...
Question 1 Report
The following pseudocode performs a linear search on an array of names to find a target name. Some lines are missing.
DECLARE Names : ARRAY[1:100] OF STRING
DECLARE Target : STRING
DECLARE Found : BOOLEAN
DECLARE Index : INTEGER
DECLARE Size : INTEGER
Size ← 100
OUTPUT "Enter name to search for: "
INPUT Target
Found ← _______________ 'Line 1
Index ← _______________ 'Line 2
WHILE _____________ AND _____________ DO 'Line 3
IF Names[Index] = Target THEN
Found ← _______________ 'Line 4
ELSE
Index ← _______________ 'Line 5
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT Target, " found at position ", Index
ELSE
OUTPUT Target, " not found"
ENDIF(a) Copy and complete lines 1 to 5 to make the algorithm work correctly. [5]
(b) State the maximum number of comparisons this algorithm would need to make if the name is not in the array. [1]
(c) Explain why a WHILE loop is used rather than a FOR loop for this search. [2]
Answer Details
(a) A linear search initialises a Found flag to FALSE and starts checking from position 1. The WHILE loop continues as long as the target has not been found AND there are still elements to check. When the target is found, Found is set to TRUE (which stops the loop). If it is not found, the index advances to the next position:
- Line 1:
Found <- FALSE- the search has not yet found the target. [1] - Line 2:
Index <- 1- begin searching from the first element. [1] - Line 3:
WHILE Index <= Size AND Found = FALSE DO- continue while there are elements left to check AND the target has not been found. Both conditions are needed: the first prevents going past the array bounds, the second stops early when found. [1] - Line 4:
Found <- TRUE- the current element matches the target. [1] - Line 5:
Index <- Index + 1- move to the next element (only when the current element does not match). [1]
(b) If the name is not in the array, the algorithm must compare every element before concluding the name is absent. With an array of 100 elements, this means 100 comparisons. [1]
(c) A WHILE loop is used because the number of iterations is not known in advance; the search should stop as soon as the target is found. [1] A FOR loop would iterate through every element regardless, performing unnecessary comparisons after the target has already been located, making it less efficient. [1] [2]
Download The App On Google Playstore
Everything you need to excel in your exams
