Linear search

Written Explanation

The idea

Think of looking for a book on an unsorted shelf. You start at one end, check each book, and stop when you find yours. If you reach the other end, it is not there.

In steps:

1. Start at index 0.
2. Compare the element at this index with the target.
3. If they are equal, stop and report this index.
4. Otherwise move to the next index.
5. If there are no more elements, report "not found".

The code

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

Three details:

• The method returns the index, not the value. The caller already knows the value; the index tells where it is.
• return i; inside the loop ends the whole method at once, so we stop looking after the first match.
• return -1; is reached only if the loop finished without finding the target. Valid array indexes start at 0, so -1 can never be mistaken for a real position. This is the convention used by many Java methods. The calling code must check for it:

int pos = linearSearch(ids, 1093);
System.out.println(pos >= 0 ? "found at " + pos : "not found");

Comparing strings

For int we compare with ==. For String values you learned that == is the wrong tool and that equals compares the text. The same loop works with a small change, here ignoring upper and lower case:

static int linearSearch(String[] a, String target) {
    for (int i = 0; i < a.length; i++) {
        if (a[i].equalsIgnoreCase(target)) return i;
    }
    return -1;
}

Two methods with the same name but different parameter types are legal: this is overloading from the methods module. Java picks the right one from the argument types.

Counting comparisons

The work of the loop is the comparison a[i] == target. How many happen depends on where the target is. For an array of n elements:

The worst case is the number to remember, because it is what you must be ready for. It is also easy to state: with 1,000 elements, 1,000 comparisons. Double the data and the worst case doubles.

To measure it instead of guessing, add a counter. A counter field makes the idea visible:

static int comparisons = 0;

static int countedSearch(int[] a, int target) {
    comparisons = 0;
    for (int i = 0; i < a.length; i++) {
        comparisons++;
        if (a[i] == target) return i;
    }
    return -1;
}

Duplicates and edge cases

• Duplicates. If the target appears more than once, this version returns the first index, because it stops at the first match. To find the last, loop from the end.
• Empty array. a.length is 0, the loop body never runs, and the method returns -1. Correct, with no special code.
• One element. Works as normal.
• Not found. Returns -1 after checking every element.

When linear search is the right choice

• The array is small. For ten items, nothing faster is worth the extra code.
• The data is not sorted and you search only once or twice. Sorting first would cost more than the search.
• You want the first match in the original order.

When the array is large, sorted, and searched many times, a better algorithm exists. That is the next lesson.