Arrays and Iteration

Linear Search

Inspect each element in order; return the first matching index, or -1 if the scan completes without a match.

Algorithm

Canonical input arr = [4, 7, 1, 9, 3, 8] with target = 9 matches at index 3 after four frames.

Basic Implementation

Basic.java 
public class Basic {
    public static void main(String[] args) {
        int[] arr = {4, 7, 1, 9, 3, 8};
        int target = 9;
        int result = linearSearch(arr, target);
        System.out.println(result);
    }

    private static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Complexity

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

Implementation notes

  • Java: explicit for loop with an early return i; from a method.
  • Never call Arrays.asList(arr).indexOf(target); the lesson is teaching the loop and the early exit.
  • The replay highlights arr[i], shows whether arr[i] == target, and flips result from -1 to i on the matching frame before returning.
linear scan Visit each element in order and compare to the target.
early return Returning as soon as a match is found avoids visiting later elements.