Validate a linear-search algorithm

Scenario. A procedure must find the first occurrence of a target number by inspecting list elements from left to right.

Inputs. A finite list L of numbers, which may be empty, and a numeric target. List positions start at 0.

Rules and notation. Output the position of the first element equal to target. If no element is equal to target, output Not found. length(L) is the number of elements in L.

Assumptions. Reading L[i] is permitted only when 0 <= i < length(L). The procedure does not change the list.

Two proposals differ only in their exit output:

Listing 1 makes the structure for validate a linear-search algorithm explicit so you can identify its required fields and boundaries.

Listing 1: Structured example of validate a linear-search algorithm.

Algorithm A                         Algorithm B
SET i TO 0                         SET i TO 0
WHILE i < length(L)                WHILE i < length(L)
    IF L[i] = target                   IF L[i] = target
        OUTPUT i                           OUTPUT i
        STOP                               STOP
    END IF                             END IF
    SET i TO i + 1                    SET i TO i + 1
END WHILE                          END WHILE
OUTPUT Not found                   OUTPUT 0

Deliverable. Select the correct proposal, explain the defect in the other, and trace the correct algorithm for L = [4, 1, 4] with targets 4 and 7. Also give the output for an empty list.

Success criteria. The algorithm returns the first matching position, reports absence only after all positions have been checked, handles an empty list without reading L[0], and terminates because i increases.

TipHint

When the loop ends normally, i = length(L) and every valid position has failed the equality test.