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.

early return Stop scanning the moment a match is found.

Basic Implementation

basic.py
Replay: real traced execution (multi-file project)
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)

  1. arr ← [4, 7, 1, 9, 3, 8]

    1arr = [4, 7, 1, 9, 3, 8]2target = 9
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    1arr = [4, 7, 1, 9, 3, 8]2target = 93result = -1
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    2target = 93result = -14for i in range(len(arr)):
    values this step-1result9target

  4. match ← no

    4for i in range(len(arr)):5    if arr[i] == target:6        result = i
    values this stepnomatch0i4arr[i]9target-1result

  5. match ← no

    4for i in range(len(arr)):5    if arr[i] == target:6        result = i
    values this stepnomatch1i7arr[i]9target-1result

  6. match ← no

    4for i in range(len(arr)):5    if arr[i] == target:6        result = i
    values this stepnomatch2i1arr[i]9target-1result

  7. match ← yes

    4for i in range(len(arr)):5    if arr[i] == target:6        result = i
    values this stepyesmatch3i9arr[i]9target-1result

  8. result ← 3

    5if arr[i] == target:6    result = i7    break
    values this step-1 → 3result

  9. stdout ← 3

    7        break8print(result)
    values this step3stdout3result

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.