Linear Search

Linear Search

Linear search is the algorithm you reach for when you have no information about the data’s order. You start at the beginning, examine each element one by one, and stop when you find what you need — or run out of elements. It is the most intuitive search algorithm, and interviewers expect you to know exactly when it is your best option and when it is not.

The Algorithm

The idea fits in one sentence: scan every element in sequence and return the index of the first match.

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

This generic version works for any reference type that implements equals. Pass in an array of String, Integer, or your own domain object — the logic stays identical.

But what if the search condition is more complex than equality? You want the first element that satisfies an arbitrary predicate. Java 25’s functional interfaces make this clean:

import java.util.function.Predicate;

public static <T> int linearSearch(T[] array, Predicate<T> condition) {
    for (int i = 0; i < array.length; i++) {
        if (condition.test(array[i])) {
            return i;
        }
    }
    return -1;
}

Now you can search for the first string longer than 10 characters, the first negative number, or the first user whose account is expired — all with the same method:

int idx = linearSearch(names, name -> name.length() > 10);

This predicate-based approach mirrors how real codebases work. Hard-coding equality into a search method limits reuse. Accepting a Predicate<T> turns the method into a general-purpose scanner.

Sentinel Optimization

Every iteration of the basic linear search performs two comparisons: one to check if the index is within bounds (i < array.length) and one to check if the element matches (array[i].equals(target)). The sentinel trick eliminates the bounds check.

The idea: place the target value at the end of the array before searching. Now you are guaranteed to find it, so the loop no longer needs to check whether it has gone past the last element.

public static int sentinelSearch(int[] array, int target) {
    int n = array.length;
    if (n == 0) return -1;

    int last = array[n - 1];
    array[n - 1] = target; // place sentinel

    int i = 0;
    while (array[i] != target) {
        i++;
    }

    array[n - 1] = last; // restore original value

    if (i < n - 1 || last == target) {
        return i;
    }
    return -1;
}

Walk through the logic:

1. Save the last element and overwrite it with the target — this is the sentinel.
2. Loop with a single comparison per iteration: array[i] != target. No bounds check needed because the sentinel guarantees termination.
3. Restore the original last element.
4. If the loop stopped before the sentinel position, the target was found at index i. If it stopped at the sentinel position, the target is found only if the original last element was the target.

This saves one comparison per iteration. On modern CPUs with branch prediction, the gain is small for most workloads. But in performance-critical inner loops that run billions of iterations — think genome sequence scanning or signal processing — removing a branch matters. The technique also demonstrates a broader principle: restructure the data to simplify the algorithm.

Interview note: You will rarely be asked to implement sentinel search directly. But mentioning it when discussing optimization shows depth of knowledge.

Complexity Analysis

Case	Comparisons	Big-O
Best	1	O(1) — target is the first element
Average	n/2	O(n) — target is equally likely at any position
Worst	n	O(n) — target is the last element or absent
Space	—	O(1) — no extra data structures

The average case assumes a uniform distribution: the target is equally likely to be at any index. Under that assumption, the expected number of comparisons is (1 + 2 + … + n) / n = (n + 1) / 2, which is O(n).

There is no way to do better in the general (unsorted) case. The adversarial argument: an adversary can always place the target in the last position you check, forcing you to examine all n elements. This gives a Ω(n) lower bound for searching unsorted data.

When Linear Search Is the Right Choice

Binary search is faster, so why would you ever choose linear search? Because binary search has preconditions that are not always met.

Unsorted Data

Binary search requires sorted input. If the data arrives unsorted and you search only once, sorting first costs O(n log n) — worse than the O(n) linear scan. Sort-then-search pays off only when you search the same data multiple times.

Linked Lists

Linked lists do not support random access. Jumping to the middle element — the first step of binary search — requires traversing half the list, which is itself O(n). Binary search on a linked list degrades to O(n log n) total comparisons, worse than a single linear pass.

Small Collections

For arrays with fewer than 10–20 elements, linear search often outperforms binary search in practice. Binary search has higher constant overhead: computing the midpoint, comparing, branching left or right. For tiny arrays, the brute-force scan finishes before binary search even completes its setup. This is why production sort implementations (like Java’s Arrays.sort) switch from merge sort to insertion sort (which uses linear search internally) for small subarrays.

Streaming Data

When elements arrive one at a time from a network socket, sensor feed, or event queue, you cannot revisit previous elements. There is no array to binary-search. You process each element as it arrives — linear search is your only option.

Finding ALL Occurrences

If you need every index where the target appears (not the first), you must examine every element regardless. Binary search finds one occurrence in O(log n), but collecting all k occurrences still requires O(log n + k) work. A linear scan accomplishes the same in a single O(n) pass with simpler code.

Finding Minimum and Maximum

A linear scan to find the minimum (or maximum) element is optimal. Here is the proof:

Theorem: Any comparison-based algorithm that finds the minimum of n elements requires at least n − 1 comparisons.

Proof: Think of each element as a participant in a tournament. An element can be confirmed as “not the minimum” only by losing a comparison — being shown to be larger than some other element. To identify the minimum, all other n − 1 elements must lose at least once. Each comparison eliminates at most one element. Therefore, at least n − 1 comparisons are required. ∎

The standard linear scan uses exactly n − 1 comparisons, matching the lower bound:

public static int findMin(int[] array) {
    int min = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] < min) {
            min = array[i];
        }
    }
    return min;
}

No algorithm — no matter how clever — can find the minimum of unsorted data with fewer than n − 1 comparisons. Linear search is provably optimal here.

Linear Search with Java Streams

Java’s Stream API provides a functional interface for linear search. Under the hood, filter and findFirst perform the same sequential scan, but the code reads more declaratively:

record Employee(String name, String department, int salary) {}

List<Employee> employees = List.of(
    new Employee("Ada", "Engineering", 120_000),
    new Employee("Grace", "Research", 135_000),
    new Employee("Alan", "Engineering", 110_000),
    new Employee("Barbara", "Research", 128_000)
);

Optional<Employee> result = employees.stream()
    .filter(e -> e.department().equals("Research") && e.salary() > 130_000)
    .findFirst();

result.ifPresent(e -> System.out.println(e.name())); // Grace

The filter + findFirst combination short-circuits: it stops as soon as it finds the first match, exactly like a hand-written loop with an early return. The Optional return type forces you to handle the “not found” case explicitly — a safer API than returning -1 or null.

For parallel streams, use findAny instead of findFirst if you do not need the first match in encounter order. findAny allows the runtime to return whichever match it discovers first across threads, improving throughput on large datasets.

Relation to Other Algorithms

Linear search is not an isolated algorithm — it is a building block embedded in many others:

• Insertion sort uses linear search to find the correct position for each element in the sorted prefix.
• Naive string matching slides a window across the text and performs a linear comparison at each position.
• Hash table collision resolution (open addressing) probes linearly through the table when collisions occur.
• Graph BFS/DFS scans adjacency lists linearly to discover neighbors.

Understanding linear search deeply means understanding the cost model of these algorithms. When insertion sort is O(n²), it is because it performs O(n) linear searches of O(n) length each.

Interviewer Tips

Linear search is rarely the standalone answer to an interview problem. Interviewers do not ask “implement linear search” as a coding question. Instead, they test whether you recognize when linear search is unavoidable:

• “Can you do better than O(n) here?” If the data is unsorted with no exploitable structure, the answer is no. Say so confidently and explain why.
• “Why not use binary search?” Have a crisp answer: “The data isn’t sorted, and sorting it first would cost more than a single linear pass.”
• “How would you optimize this?” Mention sentinel search, loop unrolling, or SIMD vectorization for primitive types — these show systems-level awareness.

The real skill is not implementing linear search. It is knowing its lower bounds and using them to argue that your solution is optimal — or to recognize when a different approach exists and you should switch to it.