Sequential search

Linear search compares the target with arr[0], then arr[1], and so on. It returns the index of the first match, or -1 if it reaches the end without one.

Invariant: before iteration i, none of arr[0..i-1] equals the target. When the loop ends without returning, the invariant covers the whole array, which proves the target is absent.

1public static int linearSearch(int[] arr, int target) {
2    for (int i = 0; i < arr.length; i++) {
3        if (arr[i] == target) {
4            return i;
5        }
6    }
7    return -1;
8}

A plain linear search does two checks per element: i < n and arr[i] == target. A sentinel search writes the target into the last slot first. The scan is then guaranteed to stop, so the loop only needs the value comparison.

After the loop, restore the original last element and decide whether we stopped on a real match or only on the planted sentinel.

• Saves one comparison per element, which mattered on older hardware and still helps in tight inner loops.
• It temporarily mutates the array, so it is unsafe on shared or read-only data and not thread-safe.
• Modern JIT compilers often remove bounds checks anyway, so measure before choosing it for speed.

1public static int sentinelSearch(int[] arr, int target) {
2    int n = arr.length;
3    int last = arr[n - 1];
4    arr[n - 1] = target;              // plant the sentinel
5    int i = 0;
6    while (arr[i] != target) {        // no bounds check needed
7        i++;
8    }
9    arr[n - 1] = last;                // restore the array
10    if (i < n - 1 || last == target) {
11        return i;
12    }
13    return -1;
14}

The cost of linear search depends on where the target is. We count comparisons because they dominate the work.

If the target is present and every position is equally likely, the expected number of comparisons is (1 + 2 + … + n) / n = (n + 1) / 2, which is still O(n).

With no ordering, sequential search is optimal: any algorithm must look at every element in the worst case, because an unexamined slot could hold the target.

For objects, compare with equals() rather than ==. == only checks whether two references point to the same object. The JDK's List.indexOf and contains are linear searches that use equals().

• Searching many times? Build a HashSet once (O(n)) and each lookup becomes O(1) on average.
• Data that stays sorted can use binary search instead, at O(log n) per lookup.

1public static <T> int indexOf(T[] items, T target) {
2    for (int i = 0; i < items.length; i++) {
3        if (Objects.equals(items[i], target)) {   // null-safe equals
4            return i;
5        }
6    }
7    return -1;
8}
9
10List<String> names = List.of("Ana", "Raj", "Lee");
11int position = names.indexOf("Raj");   // 1, linear scan using equals()
12boolean found = names.contains("Zoe"); // false after n comparisons