College Board Unit 4
How it works
Linear search walks the array comparing each element to the target and returns as soon as it finds a match. Returning the index is more useful than returning true, and -1 is the standard signal that nothing was found because it is never a valid index. The search must return -1 after the loop finishes, not inside it, since a mismatch at one position says nothing about the rest.
Return a sentinel such as negative one when nothing matches, and stop as soon as a match is found.
Common error
Returning from inside the loop on a mismatch, which reports failure after checking only the first element.
Worked example
Java
int[] values = {8, 3, 8};
int found = -1;
for (int i = values.length - 1; i >= 0 && found == -1; i--) {
if (values[i] == 8) found = i;
}
System.out.println(found);Output
2Scanning backward and stopping on the first match finds the last occurrence.
Exercises
5.4.1 · Trace
Determine the exact output. Explain the Java rule or state changes that produce it.
Java
int[] values = {4, 2, 4};
int found = -1;
for (int i = 0; i < values.length; i++) {
if (values[i] == 4) found = i;
}
System.out.println(found);Show solution
Output
2Without an early return or stop condition, later matching positions overwrite earlier ones.
5.4.2 · Write code
Write public static int firstIndex(int[] values, int target). Return the first matching index, or -1 when absent.
Show solution
One valid solution is shown below. Other implementations satisfying the contract are also valid.
Java
public static int firstIndex(int[] values, int target) {
for (int i = 0; i < values.length; i++) {
if (values[i] == target) return i;
}
return -1;
}Check your code
Java
System.out.println(firstIndex(new int[]{6,2,6}, 6));
System.out.println(firstIndex(new int[]{}, 6));
System.out.println(firstIndex(new int[]{1,2}, 6));Expected output
0
-1
-1