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.

Basic Implementation

basic.f90 
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

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.
early exit Stop scanning the moment a match is found.