Linear Search in Java

When you look for your friend in a school assembly line, you start at one end and look at each face until you find them. You don't need the line to be in any order, and you don't need any special trick. That is linear search: the simplest searching algorithm there is, and still the right one surprisingly often. In this lesson, you will learn how linear search works, write it in Java for arrays and for any type, trace it step by step, and see its cost and the cases where it is the best choice.

What Is Linear Search?

Linear search in Java is a searching algorithm that is used to find a target value by checking each element one by one, from the first to the last, until it finds a match or reaches the end. It is also called sequential search.

• It works on any array or list, sorted or not.
• It returns the index of the first match, or -1 if the target isn't there.
• It needs no extra memory.

How It Works

1. Start at index 0.
2. Compare the element with the target.
3. If they match, return the index.
4. Otherwise, move to the next index and repeat.
5. If you reach the end, return -1.

Linear Search on an Array

Let's see an example that searches for a roll number and prints each comparison.

public class LinearSearch {
    static int linearSearch(int[] values, int target) {
        for (int i = 0; i < values.length; i++) {
            System.out.println("  check index " + i + ": " + values[i]);
            if (values[i] == target) {
                return i;
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        int[] rollNumbers = {41, 17, 8, 33, 26, 12};
 
        System.out.println("Searching for 33");
        System.out.println("Found at index " + linearSearch(rollNumbers, 33));
 
        System.out.println("Searching for 50");
        System.out.println("Found at index " + linearSearch(rollNumbers, 50));
    }
}

Searching for 33
  check index 0: 41
  check index 1: 17
  check index 2: 8
  check index 3: 33
Found at index 3
Searching for 50
  check index 0: 41
  check index 1: 17
  check index 2: 8
  check index 3: 33
  check index 4: 26
  check index 5: 12
Found at index -1

Explanation:

1. The search for 33 checks indexes 0 to 3 and stops at the match: 4 comparisons.
2. The search for 50 checks all 6 elements and returns -1, the usual "not found" value in Java (the same one String.indexOf and List.indexOf use).
3. The array isn't sorted, and it doesn't need to be.

A Generic Version

The same idea works for any type, as long as you compare with equals instead of ==.

import java.util.List;
import java.util.Objects;
 
public class FindStudent {
    static <T> int indexOf(List<T> items, T target) {
        for (int i = 0; i < items.size(); i++) {
            if (Objects.equals(items.get(i), target)) {
                return i;
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        List<String> names = List.of("Srihitha", "Advitha", "Navika");
        System.out.println(indexOf(names, "Navika"));
        System.out.println(indexOf(names, "Anamaneni"));
        System.out.println(names.indexOf("Navika"));   // the JDK's version
    }
}

2
-1
2

Explanation: Objects.equals compares contents and is safe if an element is null. The JDK's List.indexOf does exactly this, which is why it gives the same answer.

Complexity

When to Use It

In the JDK, linear search sits behind List.indexOf, List.contains, String.indexOf and the stream method filter(...).findFirst().

Common Mistakes

Using == for objects. It compares references; use equals.

Returning inside the loop too early. Writing else return -1; inside the loop gives up after checking only the first element.

Off-by-one in the loop. i <= values.length reads past the end and throws ArrayIndexOutOfBoundsException.

Using it in a loop over large data. A linear search inside another loop is O(n²).

Practice

1. Easy: Write lastIndexOf(int[] values, int target) that returns the index of the last match. Test it on {5, 3, 5, 1} with target 5.
2. Harder: Write countMatches(int[] marks, int minimum) that returns how many marks are at least minimum, and firstFailing(int[] marks) that returns the index of the first mark below 35, or -1.

Key Takeaways