Linear search algorithm

Which of the following flowcharts correctly represents a linear search algorithm that searches for a specific number called target in a list entitled L? Given a list L and a number target, the algorithm should output “Number found” if target is in the list L, and “Number not found” otherwise.

For example:

  • if L = [1, 2, 3, 4, 5] and target = 3, the algorithm should output “Number found”.
  • if L = [1, 2, 3, 4, 5] and target = 6, the algorithm should output “Number not found”.

You can assume that the list L is:

  • Indexed starting from 0.
  • Non-empty.

Choose the correct flowchart from the options below:

  • Flowchart in Figure 1 (a)
  • Flowchart in Figure 1 (b)
  • Flowchart in Figure 1 (c)
  • Flowchart in Figure 1 (d)

Figure 1 groups the four candidate flowcharts for comparison.

graph LR
    accTitle: Linear-search candidate A
    accDescr: The index starts at zero. If it equals the list length, Number not found is output. Otherwise a match outputs Number found, and a mismatch adds one to the index and returns to the first decision.
    A((Start)) --> IN[/L, target/]
    IN --> B["Set i to 0"]
    B --> C{"Is i<br>equal to<br>L length?"}
    C -- Yes --> D[/Number not found/]
    C -- No --> E{"Is L[i]<br>equal to<br>target?"}
    E -- Yes --> F[/Number found/]
    E -- No --> G[Increment i by 1]
    G --> C
    D --> H((End))
    F --> H
(a) Candidate A. 
graph LR
    accTitle: Linear-search candidate B
    accDescr: The index starts at zero. If it is not less than the list length, Number found is output. Otherwise a match outputs Number found, and a mismatch adds one to the index and returns to the first decision.
    A((Start)) --> IN[/L, target/]
    IN --> B[Set i to 0]
    B --> C{"Is i<br>less than<br>L length?"}
    C -- No --> D[/Number found/]
    C -- Yes --> E{"Is L[i]<br>equal to<br>target?"}
    E -- Yes --> F[/Number found/]
    E -- No --> G[Increment i by 1]
    G --> C
    D --> H((End))
    F --> H
(b) Candidate B. 
graph LR
    accTitle: Linear-search candidate C
    accDescr: The index starts at zero. If it equals zero, Number not found is output. Otherwise a match outputs Number found, and a mismatch subtracts one from the index and returns to the first decision.
    A((Start)) --> IN[/L, target/]
    IN --> B[Set i to 0]
    B --> C{"Is i<br>equal to 0?"}
    C -- Yes --> D[/Number not found/]
    C -- No --> E{"Is L[i]<br>equal to<br>target?"}
    E -- Yes --> F[/Number found/]
    E -- No --> G[Decrement i by 1]
    G --> C
    D --> H((End))
    F --> H
(c) Candidate C. 
graph LR
    accTitle: Linear-search candidate D
    accDescr: The index starts at zero. If it is not greater than zero, Number not found is output. Otherwise a match outputs Number found, and a mismatch subtracts one from the index and returns to the first decision.
    A((Start)) --> IN[/L, target/]
    IN --> B[Set i to 0]
    B --> C{"Is i<br>greater than 0?"}
    C -- No --> D[/Number not found/]
    C -- Yes --> E{"Is L[i]<br>equal to<br>target?"}
    E -- Yes --> F[/Number found/]
    E -- No --> G[Decrement i by 1]
    G --> C
    D --> H((End))
    F --> H
(d) Candidate D.
Figure 1: Linear Search Algorithm (Question 1).