CSCD210

Linear search

Skillcscd210-linear-searchTextbookBJP Ch 7

Linear search: walk and compare

Student can produce a linear-search method that returns the index of the first matching element, or a sentinel value when no element matches; and choose the correct comparison operator (== for primitives, .equals(...) for object types).

Linear search is the simplest find-the-target algorithm. Walk every slot in order; compare each element to the target; return when a match is found.

public static int indexOf(final int[] xs, final int target) {
    for (int i = 0; i < xs.length; i++) {
        if (xs[i] == target) {
            return i;
        }
    }
    return -1;             // (the -1 not-found convention)
}

Three features distinguish this from the common array algorithms:

1. The loop can exit before the last slot. As soon as a match is found, the return i; jumps out of the method: no break, no flag, no remaining iterations. Average runtime on a random array is n/2 comparisons; worst case (target absent) is n. 2. The loop variable's value at exit is the answer. Sum, count, and best-so-far loops compute the answer in an accumulator. Linear search's answer is the index i at the moment the match was found. 3. The not-found case is real. Every other common array algorithm returns a well-defined value regardless of the input. Linear search has two outcomes: "found, here is the index" and "not found." The not-found sentinel convention handles the "not found" return value.

The traditional for is required here because the answer is the index, not the value. The three-condition fit test rules the enhanced-for out here, and why an index-returning search in particular cannot use it is spelled out below.

Searching for objects: use .equals, not ==

For arrays of objects (String[], Pet[], anything not a primitive), the comparison must be .equals(target), not ==:

public static int indexOf(final String[] xs, final String target) {
    for (int i = 0; i < xs.length; i++) {
        if (xs[i].equals(target)) {     // .equals, not ==
            return i;
        }
    }
    return -1;
}

== on String compares references: true only when both names refer to the same heap object. .equals compares contents: true when the strings have the same characters. The rule that equality on strings uses .equals covers this, and linear search is the place students first see the consequence in array code.

A safer form puts the constant on the left: target.equals(xs[i]). This avoids NullPointerException if a slot is null (assuming target itself is not null). The CSCD 210 lab style does not require this defensive ordering, but production code often does.

In other languages

  • Python: xs.index(target) is the built-in (raises ValueError on miss; the in-place check if target in xs is the boolean version).
  • C: identical loop pattern; strcmp is the analog of .equals for C strings (char[]).
  • Java standard library: Arrays.asList(xs).indexOf(target) (autoboxes), List.of(xs).indexOf(target) (immutable). For raw int[], no built-in indexOf exists; the loop is the answer.

The -1 not-found convention

Student can explain why -1 is the standard "not found" sentinel for index-returning search methods, recognize it in JDK method signatures (String.indexOf, Arrays.binarySearch's non-standard variant), and write caller code that tests idx >= 0 rather than idx != -1.

Linear search (and String.indexOf, and most index-returning methods in the JDK) returns -1 when the target is absent. The choice is a convention, not a language requirement: any value the caller can distinguish from a valid result would work. The convention exists because of three facts about array indices:

1. Indices are non-negative. Valid indices are 0, 1, …, length - 1. There is no negative valid index. 2. -1 is impossible to confuse with a real index. A test if (found >= 0) reads as "we found something at a real position." 3. The JDK uses -1 everywhere it can. String.indexOf, String.lastIndexOf, Arrays.binarySearch (with a different sign convention, described below), ArrayList.indexOf. Matching the JDK convention is what every Java developer expects.

final int idx = indexOf(xs, target);
if (idx >= 0) {
    System.out.println("found at index " + idx);
} else {
    System.out.println("not found");
}

The body of an if (idx == -1) and if (idx >= 0) test the same condition, but >= 0 is the recommended form: it reads as a statement about the meaningful case ("we found something") rather than the failure case.

Why not throw an exception instead?

A method that cannot find its target could throw NoSuchElementException rather than return a sentinel. Two reasons CSCD 210 prefers the sentinel:

  • Performance. Exceptions are expensive to construct (stack-trace capture); for a search method that runs in inner loops, the sentinel is much cheaper.
  • Semantic fit. "Not found" is a common, expected outcome of a search, not an exceptional one. Bloch's Effective Java Item 70 distinguishes: "use checked exceptions for recoverable conditions and runtime exceptions for programming errors"; an absent target is neither: it is a routine result.

JDK Map.get returns null for a missing key (the same pattern: sentinel, not exception). The Java 8 Optional<T> family was added precisely to give a third option (Optional.empty()) that signals absence without a magic value, but CSCD 210 stops at the sentinel.

A subtlety in the Arrays.binarySearch sign convention

Arrays.binarySearch does not return -1 for "not found." It returns a negative number that encodes the insertion point: the slot where the missing target should be inserted to keep the array sorted. The decoding formula is -(insertionPoint) - 1. This is a distinct convention; do not assume -1 means "not found" universally. The treatment of the built-in Arrays.binarySearch covers this in detail.

In other languages

  • Python: list.index(target) raises ValueError on miss; the sentinel-style alternative is target in list (boolean) or writing your own loop.
  • C: strchr / strstr return NULL (pointer sentinel) on miss; bsearch returns NULL on miss.
  • C# / .NET: Array.IndexOf and List<T>.IndexOf both return -1. Matches Java.
  • Go: typically returns the index as int and a bool ok flag: two-return-value convention.

Why indexOf cannot use the enhanced-for

Student can identify linear search (an index-returning method) as a case where the enhanced-for does not fit, recognize the inferior "external counter inside enhanced-for" alternative as the wrong workaround, and distinguish indexOf (needs index) from contains (does not).

Linear search is the canonical case where the enhanced-for does not fit. The method returns the index of the match, and the enhanced-for hides the index by design. There is no clean way to expose the index from inside an enhanced-for body.

//  Tempting but broken: the loop variable is the VALUE, not the index
public static int indexOf(final int[] xs, final int target) {
    for (int v : xs) {
        if (v == target) {
            return ???;        //  what do I return? `v` is the value, not the index
        }
    }
    return -1;
}

The students who attempt this typically reach for a manual counter:

//  Works but worse than the traditional for
public static int indexOf(final int[] xs, final int target) {
    int i = 0;
    for (int v : xs) {
        if (v == target) {
            return i;
        }
        i++;
    }
    return -1;
}

Two problems with the counter-inside-for-each form:

1. It is longer than the traditional for. The fake counter has to be declared (outside the loop) and incremented (inside the loop). A traditional for does both in the header. 2. A future maintainer can break it. A continue or break inserted into the body bypasses the i++; and the counter desynchronizes silently. Selection sort never has this risk because its index variable is in the header.

The right answer is to use the loop form whose feature set matches the task. Linear search needs the index; therefore use the traditional for.

The fit test recap

The three-condition fit test covered this in the abstract, and linear search is the concrete case where condition 2 (no index needed) fails. The other common array algorithms (sum, count, min, max) satisfy all three conditions and use the enhanced-for naturally.

Search is the boundary case students remember: "the algorithm whose loop form is not the enhanced-for."

What if I really want to use the enhanced-for?

The pattern that works without an external counter is to return a boolean (contains, not indexOf):

public static boolean contains(final int[] xs, final int target) {
    for (int v : xs) {
        if (v == target) {
            return true;
        }
    }
    return false;
}

contains answers a different question: "is the target present?" rather than "where is the target?": and the enhanced-for fits because the return value does not depend on position. If the caller actually needs the index, contains is the wrong method. The two have different signatures and different uses.

In other languages

  • Python: for i, v in enumerate(xs): gives both the index and the value. Java has no built-in enumerate.
  • C++: range-based for has the same limitation; the iterator-based form is the alternative.
  • Rust: for (i, v) in xs.iter().enumerate() is the standard pattern for "index plus value."
  • Java: no enumerate. The traditional for is the way.