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.

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.

Basic Implementation

Basic.java
Replay: real traced execution (multi-file project)
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;
    }
}

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

    2public static void main(String[] args) {3    int[] arr = {4, 7, 1, 9, 3, 8};4    int target = 9;
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    3int[] arr = {4, 7, 1, 9, 3, 8};4int target = 9;5int result = linearSearch(arr, target);
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    4int target = 9;5int result = linearSearch(arr, target);6System.out.println(result);
    values this step-1result9target

  4. match ← no

    10for (int i = 0; i < arr.length; i++) {11    if (arr[i] == target) {12        return i;
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    10for (int i = 0; i < arr.length; i++) {11    if (arr[i] == target) {12        return i;
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    10for (int i = 0; i < arr.length; i++) {11    if (arr[i] == target) {12        return i;
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    10for (int i = 0; i < arr.length; i++) {11    if (arr[i] == target) {12        return i;
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    11if (arr[i] == target) {12    return i;13}
    values this step3result3i

  9. stdout ← 3

    5    int result = linearSearch(arr, target);6    System.out.println(result);7}
    values this step3stdout3result

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.