TOPIC 4.14 · STUDY

Searching Algorithms

Linear search walks a 1D array from index 0, comparing each element to a target until it finds a match or runs out of cells. It returns the first matching index, or -1 when the target is missing. Every equality test counts as a comparison, and the array does not need to be sorted.

4.14.A

Linear search of a 1D array

Linear search looks for a target value by checking elements one at a time in order. Start at index 0. Compare the element at that index to the target. For int values, the comparison uses ==. If they match, return that index and stop. If not, move to the next index and try again. When the loop finishes with no match, the usual result is -1.

The search stops at the first match, so later copies of the same value are never visited. Each equality test counts as one comparison, including the successful one. A miss still compares every element before returning -1. The array does not need to be sorted; order only decides which cells are checked first.

public static int findBay(int[] bays, int target) {
    for (int i = 0; i < bays.length; i++) {
        if (bays[i] == target) {
            return i;
        }
    }
    return -1;
}

int[] bays = {3, 8, 5, 2};
System.out.print(findBay(bays, 5));  // 2 after three comparisons
System.out.print(findBay(bays, 9));  // -1 after four comparisons

For target 5, index 0 compares 3 (no), index 1 compares 8 (no), and index 2 compares 5 (yes), so the method returns 2 after three comparisons. For target 9, every cell is checked and none match, so the method returns -1 after four comparisons.

Four array cells hold 3, 8, 5, and 2. An arrow points to the matching cell at index 2 that holds 5.

Left-to-right search of {3, 8, 5, 2} for target 5 stops at index 2. The arrow marks the first match.

Key points

  • Linear search starts at index 0 and checks each next index in order.
  • Compare ints with ==; stop and return the index of the first match.
  • If the target is missing, return -1 after checking every element.
  • Every equality test counts as a comparison, including the match.
  • The array does not need to be sorted for linear search.

A missing target is not index 0. When the value never appears, the usual result is -1 after every element has been compared.

Practice this topic