Studyledge

Advanced Algorithms and Recursion: Question 6

Syllabus 19.1

Structured A2 8 marks

A programmer writes the following function to search an array of student ID numbers using linear search.

FUNCTION LinearSearch(Arr : ARRAY[1:8] OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index : INTEGER
    FOR Index ← 1 TO 8
        IF Arr[Index] = Target THEN
            RETURN Index
        ENDIF
    NEXT Index
    RETURN -1
ENDFUNCTION

The array currently holds Arr = [23, 47, 12, 89, 56, 34, 78, 61] (index 1 to index 8).

(a) State the values of Index checked, the number of comparisons made, and the value returned, when LinearSearch(Arr, 56) is called. [3]

(b) State the number of comparisons made and the value returned when LinearSearch(Arr, 99) is called, explaining why every element of Arr must be checked in this case. [3]

(c) State one precondition that must be satisfied about the contents of an array before binary search could correctly be used to search it, and explain whether this precondition is currently satisfied for Arr. [2]

Show worked solution Hide worked solution

Worked solution

Part (a): Tracing LinearSearch(Arr, 56)

LinearSearch checks each array position in turn, starting at Index = 1, comparing Arr[Index] against Target until a match is found:

IndexArr[Index]Arr[Index] = 56 ?
123No
247No
312No
489No
556Yes, RETURN 5

The comparison at Index = 5 succeeds, so the loop stops immediately and the function returns.

[3 marks]: [1] for correctly listing Index = 1, 2, 3, 4, 5 as the positions checked, [1] for the correct comparison count (5), [1] for the correct returned value (5).

Part (b): Tracing LinearSearch(Arr, 99)

No element of Arr equals 99, so every comparison from Index = 1 to Index = 8 fails:

IndexArr[Index]Arr[Index] = 99 ?
123No
247No
312No
489No
556No
634No
778No
861No

Because IF Arr[Index] = Target THEN RETURN Index is never triggered, NEXT Index runs after every iteration and the FOR loop completes fully. Control then reaches the statement after the loop, RETURN -1.

[3 marks]: [1] for recognising the loop must run all 8 iterations when the target is absent, [1] for the correct comparison count (8), [1] for the correct returned value (-1) with a valid explanation.

Binary search only works correctly if the data it searches is already sorted (in either ascending or descending order), since it repeatedly compares the target against a middle element and discards the half of the array that cannot contain the target. A decision that is only valid if the array’s order is known in advance.

Arr = [23, 47, 12, 89, 56, 34, 78, 61] is not sorted: for example, Arr[2] = 47 is greater than Arr[3] = 12, so values do not increase (or decrease) consistently along the array. Binary search could not be applied directly to Arr in its current order. It would first need to be sorted.

[2 marks]: [1] for correctly stating the precondition (the array must be sorted), [1] for correctly explaining that Arr does not currently satisfy it, with a valid example.

Final answers

  • (a) Index values checked: 1, 2, 3, 4, 5. Comparisons: 5. Returned value: 5.
  • (b) Comparisons: 8. Returned value: -1.
  • (c) Precondition: the array must be sorted. Arr does not satisfy this (e.g. Arr[2] > Arr[3]).