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