Studyledge

Algorithm Design and Standard Methods: Question 3

Syllabus 7.3, 7.4

Structured 9 marks

A community makerspace keeps a one-dimensional (1D) array called ToolID, with 10 elements, listing the ID numbers of tools that are currently checked out. Before letting a member borrow tool number 7749, the system must search ToolID to see if it is already checked out.

The array currently holds these values:

Index 1 2 3 4 5 6 7 8 9 10
ToolID 4471 2280 9963 5017 3382 7749 1206 8890 6644 2953

(a) Write an algorithm, in pseudocode, that uses a linear search to search ToolID for the value stored in SearchValue. If the value is found, your algorithm should output the index position at which it was found. If it is not found after every element has been checked, your algorithm should output the message "Not checked out". [4]

(b) SearchValue is set to 7749. Trace your algorithm, showing the value of Index and the value of ToolID[Index] compared at each step, until the algorithm ends. [3]

(c) State the number of comparisons your algorithm makes before it ends, and explain why the number of comparisons a linear search needs to make can vary considerably each time it searches this array. [2]

Show worked solution Hide worked solution

Worked solution

Part (a): Writing the linear search algorithm

The array is not sorted, so a linear search must check each element in turn, starting from the first, stopping as soon as a match is found or the end of the array is reached:

DECLARE ToolID : ARRAY[1:10] OF INTEGER
DECLARE SearchValue : INTEGER
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN

Index ← 1
Found ← FALSE
WHILE Index <= 10 AND Found = FALSE
    IF ToolID[Index] = SearchValue THEN
        Found ← TRUE
        OUTPUT Index
    ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = FALSE THEN
    OUTPUT "Not checked out"
ENDIF

Mark-earning features: [1] Index initialised to 1 and Found initialised to FALSE; [1] a loop that continues only while Index <= 10 AND Found = FALSE; [1] a correct comparison ToolID[Index] = SearchValue that sets Found and outputs Index on a match, else increments Index; [1] the message "Not checked out" output only once the loop has ended without a match.

Part (b): Tracing the algorithm for SearchValue = 7749

IndexToolID[Index]Comparison with 7749Action
14471not equalIndex ← 2
22280not equalIndex ← 3
39963not equalIndex ← 4
45017not equalIndex ← 5
53382not equalIndex ← 6
67749equalFound ← TRUE, OUTPUT 6

As soon as Found becomes TRUE, the WHILE condition Found = FALSE is no longer true, so the loop ends immediately after index 6 is output.

Part (c): Number of comparisons and why it varies

Counting the IF ToolID[Index] = SearchValue comparisons in the trace above gives 6 comparisons (at indices 1 to 6) before the algorithm ends.

This number depends entirely on the position of the value being searched for:

  • If a member later searches for tool 4471 (at index 1), the search would end after just 1 comparison.
  • If a member searches for tool 2953 (at index 10), or for a tool number that is not checked out at all, the search would need to check all 10 elements before it could finish.

A linear search has no way of knowing in advance where a value is stored, so it must check elements one at a time from the start of the array. Meaning the number of comparisons can be anywhere from 1 up to the full length of the array.

Final answers

  • (a) See the pseudocode algorithm above.
  • (b) Indices 1–5 do not match 7749; index 6 matches, so 6 is output.
  • (c) 6 comparisons; the count varies because it depends on the position (or absence) of the search value in the array.