Arrays and Iteration

Linear Search

Inspect each element in order and return the first matching index. If the scan completes without a match, return -1. Demonstrates the early-return pattern and the not-found fall-through.

Algorithm

The canonical found run uses target = 9, which lives at index 3. The spec's second canonical run (target = 2) walks the full array and falls through to -1.

Basic Implementation

basic.py 
arr = [4, 7, 1, 9, 3, 8]
target = 9
result = -1
for i in range(len(arr)):
    if arr[i] == target:
        result = i
        break
print(result)

Complexity

  • Time: O(n) worst case
  • Space: O(1)

Implementation notes

  • Python: write the explicit for i in range(len(arr)) form and break after assigning result = i. Calling arr.index(target) would hide the index walk.
  • The replay shows i, arr[i], and the boolean match result on every step, matching the lesson spec's state-transition table for the found-case run.
early return Stop scanning the moment a match is found.