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-exit pattern and the not-found fall-through.

Algorithm

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

early exit Stop scanning the moment a match is found.

Basic Implementation

basic.f90
Replay: real traced execution (multi-file project)
program linear_search
    implicit none
    integer :: arr(6) = [4, 7, 1, 9, 3, 8]
    integer :: target, result, i
    target = 9
    result = -1
    do i = 1, 6
        if (arr(i) == target) then
            result = i
            exit
        end if
    end do
    print '(I0)', result
end program linear_search

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

    2implicit none3integer :: arr(6) = [4, 7, 1, 9, 3, 8]4integer :: target, result, i
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    4integer :: target, result, i5target = 96result = -1
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    5target = 96result = -17do i = 1, 6
    values this step-1result9target

  4. match ← no

    7do i = 1, 68    if (arr(i) == target) then9        result = i
    values this stepnomatch1i4arr(i)9target

  5. match ← no

    7do i = 1, 68    if (arr(i) == target) then9        result = i
    values this stepnomatch2i7arr(i)9target

  6. match ← no

    7do i = 1, 68    if (arr(i) == target) then9        result = i
    values this stepnomatch3i1arr(i)9target

  7. match ← yes

    7do i = 1, 68    if (arr(i) == target) then9        result = i
    values this stepyesmatch4i9arr(i)9target

  8. result ← 4

    8if (arr(i) == target) then9    result = i10    exit
    values this step4result4i

  9. stdout ← 4

    12    end do13    print '(I0)', result14end program linear_search
    values this step4stdout4result

Complexity

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

Implementation notes

  • Fortran: write the explicit do i = 1, n loop and exit from the loop as soon as the match fires. Calling findloc(arr, target) would hide the index walk the lesson is teaching.
  • 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.