Chapter 12 of 65

Linear Search

Imagine your friend hands you a shuffled deck of exam answer sheets and asks you to find the sheet with roll number 27.

The sheets are not in any order. So what do you do?

You pick up the first sheet and check it. Not 27? Put it aside and check the next one. You keep going one by one until you either find roll number 27 or run out of sheets.

That simple, natural strategy is called Linear Search.

It is the very first searching algorithm every programmer learns, and even though it is simple, it shows up everywhere: in interview questions, inside library methods like indexOf(), and as a building block for more complex algorithms.


Linear Search is a searching algorithm that checks every element of a collection one by one, from start to end, until the target element is found or the collection ends.

It is also called Sequential Search, because it goes through the elements in sequence.

The idea in one line:

Start at the first element → compare → move to the next → repeat

The algorithm gives back:

  • The index of the element if it is found

  • -1 if the element is not present (because -1 can never be a valid array index)

You already saw a small version of this in the Arrays chapter when we checked whether a value exists in an array. In this chapter we will study it properly: how it works, its variations, its complexity and where it is the right (and wrong) choice.


How Linear Search Works

Let's say we have this array:

Index:   0    1    2    3    4    5
Value:  14    7   32    9   21    5

We want to find 9.

Step 1

Index 0 → 14
14 == 9 ? No → move ahead

Step 2

Index 1 → 7
7 == 9 ? No → move ahead

Step 3

Index 2 → 32
32 == 9 ? No → move ahead

Step 4

Index 3 → 9
9 == 9 ? Yes → Found at index 3

We stop as soon as we find the element. We do not look at indexes 4 and 5.

Now suppose we search for 50:

14 → no
7  → no
32 → no
9  → no
21 → no
5  → no

Reached the end → return -1

When the element is missing, we are forced to check every single element before we can say "not found".


The Algorithm

Written as simple steps:

1. Start from index 0.
2. Compare the current element with the target.
3. If they are equal, return the current index.
4. Otherwise, move to the next index.
5. If you reach the end of the array, return -1.

Notice that there is no requirement for the array to be sorted. Linear search works on any order of data.


Linear Search in Java

class Main {

    static int linearSearch(int[] arr, int target) {

        for (int i = 0; i < arr.length; i++) {

            if (arr[i] == target) {
                return i;      // found it, return the index
            }
        }

        return -1;             // checked everything, not found
    }

    public static void main(String[] args) {

        int[] numbers = {14, 7, 32, 9, 21, 5};

        System.out.println("Index of 9: " + linearSearch(numbers, 9));
        System.out.println("Index of 14: " + linearSearch(numbers, 14));
        System.out.println("Index of 50: " + linearSearch(numbers, 50));
    }
}

Output:

Index of 9: 3
Index of 14: 0
Index of 50: -1

Two details are worth noticing:

  • return i is inside the loop. The moment we find the target, we leave the method.

  • return -1 is after the loop. We only reach it when the loop has checked every element without success.


Counting the Comparisons

To really understand the cost of linear search, let's count how many comparisons it makes for different targets.

class Main {

    static int comparisons = 0;

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

    public static void main(String[] args) {

        int[] arr = {8, 3, 6, 1, 9};

        int[] targets = {8, 1, 9, 4};

        for (int t : targets) {
            int index = linearSearch(arr, t);
            System.out.println("Target " + t + " -> index " + index
                    + ", comparisons = " + comparisons);
        }
    }
}

Output:

Target 8 -> index 0, comparisons = 1
Target 1 -> index 3, comparisons = 4
Target 9 -> index 4, comparisons = 5
Target 4 -> index -1, comparisons = 5

This small experiment shows the three cases very clearly:

  • Target at the front → only 1 comparison

  • Target at the end → n comparisons

  • Target missing → also n comparisons


Time and Space Complexity

Let n be the number of elements.

Best Case — O(1)

The target is the very first element. We make just one comparison.

[8, 3, 6, 1, 9]   search 8
 ↑
found immediately

Worst Case — O(n)

The target is the last element, or it is not present at all. We must check all n elements.

[8, 3, 6, 1, 9]   search 4
 ↑  ↑  ↑  ↑  ↑
checked everything → not found

Average Case — O(n)

If the target is equally likely to be at any position, on average we check about half the array:

(1 + 2 + 3 + ... + n) / n = (n + 1) / 2

That is roughly n/2 comparisons. As we learned in the Time Complexity chapter, we drop constants, so n/2 is still O(n).

Space Complexity — O(1)

The iterative version uses only a loop variable, no matter how big the array is. So the extra space is constant.

Case

Comparisons

Time

Best

1

O(1)

Average

about n/2

O(n)

Worst

n

O(n)

Extra space

—

O(1)

Using the notations from the Big O, Big Ω & Big Θ chapter, linear search is O(n) in the worst case and Ω(1) in the best case.


In real problems, "find the element" can mean many different things. The good news is that all of them are small changes to the same loop.

1. First Occurrence

The basic version already returns the first index where the target appears, because it scans from the left and stops at the first match.

2. Last Occurrence

Scan from the right end instead:

static int lastIndex(int[] arr, int target) {
    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

3. Count Occurrences

Here we must not stop at the first match. We go through the whole array and count:

static int countOccurrences(int[] arr, int target) {
    int count = 0;
    for (int value : arr) {
        if (value == target) {
            count++;
        }
    }
    return count;
}

This always takes O(n), even in the best case, because we can't know whether more matches exist until we reach the end.

4. All Indexes

Same idea, but we store every matching index in a list:

static List<Integer> allIndexes(int[] arr, int target) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            result.add(i);
        }
    }
    return result;
}

5. Searching Strings

For objects such as String, compare with equals(), not ==. (We discussed why in the Strings chapter: == compares references, equals() compares content.)

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

Using what we learned in the Recursion chapter, we can also write linear search recursively. There are two base cases: we ran out of elements, or we found the target.

static int searchRecursive(int[] arr, int target, int index) {
    if (index == arr.length) {
        return -1;                      // base case: nothing left
    }
    if (arr[index] == target) {
        return index;                   // base case: found
    }
    return searchRecursive(arr, target, index + 1);
}

This is a nice recursion exercise, but in practice the loop version is better. The recursive version uses O(n) stack space and can cause a StackOverflowError on very large arrays.


A Complete Example

Let's put all these variations together in one program:

import java.util.ArrayList;
import java.util.List;

class Main {

    // Index of the first occurrence, or -1
    static int firstIndex(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    // Index of the last occurrence, or -1
    static int lastIndex(int[] arr, int target) {
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    // How many times target appears
    static int countOccurrences(int[] arr, int target) {
        int count = 0;
        for (int value : arr) {
            if (value == target) {
                count++;
            }
        }
        return count;
    }

    // Every index where target appears
    static List<Integer> allIndexes(int[] arr, int target) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                result.add(i);
            }
        }
        return result;
    }

    // Search in an array of Strings
    static int searchName(String[] names, String target) {
        for (int i = 0; i < names.length; i++) {
            if (names[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }

    // Recursive linear search
    static int searchRecursive(int[] arr, int target, int index) {
        if (index == arr.length) {
            return -1;                      // base case: nothing left
        }
        if (arr[index] == target) {
            return index;                   // base case: found
        }
        return searchRecursive(arr, target, index + 1);
    }

    public static void main(String[] args) {

        int[] marks = {72, 85, 64, 85, 90, 85, 58};

        System.out.println("Marks: [72, 85, 64, 85, 90, 85, 58]");
        System.out.println("First 85 at index: " + firstIndex(marks, 85));
        System.out.println("Last 85 at index: " + lastIndex(marks, 85));
        System.out.println("85 appears " + countOccurrences(marks, 85) + " times");
        System.out.println("All indexes of 85: " + allIndexes(marks, 85));
        System.out.println("Recursive search for 90: " + searchRecursive(marks, 90, 0));
        System.out.println("Recursive search for 100: " + searchRecursive(marks, 100, 0));

        String[] names = {"Aarav", "Diya", "Kabir", "Meera"};
        System.out.println("Kabir found at index: " + searchName(names, "Kabir"));
        System.out.println("Rohan found at index: " + searchName(names, "Rohan"));
    }
}

Output:

Marks: [72, 85, 64, 85, 90, 85, 58]
First 85 at index: 1
Last 85 at index: 5
85 appears 3 times
All indexes of 85: [1, 3, 5]
Recursive search for 90: 4
Recursive search for 100: -1
Kabir found at index: 2
Rohan found at index: -1

Linear Search in Java's Built-in Methods

You have probably already used linear search without realising it. Many Java methods scan elements one by one internally:

Method

What it does

Time

String.indexOf(ch)

First index of a character

O(n)

ArrayList.indexOf(obj)

First index of an element

O(n)

ArrayList.contains(obj)

Calls indexOf internally

O(n)

LinkedList.contains(obj)

Walks node by node

O(n)

So when you write list.contains(x) inside a loop that runs n times, you are actually writing an O(n²) algorithm. This is a very common hidden performance problem in interview solutions.


Common Mistakes

1. Returning -1 Too Early

This is the most common bug beginners write:

// WRONG
static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        } else {
            return -1;   // gives up after checking only arr[0]
        }
    }
    return -1;
}

If the first element is not the target, this method immediately returns -1 without checking the rest. The "not found" answer must come after the loop finishes.

2. Using == for Strings

names[i] == target        // compares references (may be false even if text is same)
names[i].equals(target)   // compares the actual text (correct)

3. Off-by-One Loop Bounds

Writing i <= arr.length instead of i < arr.length will try to read arr[arr.length] and throw an ArrayIndexOutOfBoundsException.

4. Stopping When You Should Not

For "count" or "find all" problems, you must scan the full array. Putting a return or break on the first match gives a wrong answer.


Linear search is the right choice when:

  • The data is unsorted and you search only once or a few times

  • The collection is small (for a few dozen elements, linear search is often as fast as anything else)

  • The data structure does not allow random access, such as a linked list

  • You need to check a condition rather than an exact value, for example "the first student who scored below 40"

It is the wrong choice when:

  • The data is large and already sorted — binary search is much faster

  • You need to search the same data many times — it is usually better to sort it once, or store it in a hash-based structure

Here is a quick preview of the difference, which we will explore in the next chapter:

Number of elements

Linear search (worst case)

Binary search (worst case)

1,000

1,000 comparisons

about 10 comparisons

1,000,000

1,000,000 comparisons

about 20 comparisons

But remember: binary search only works on sorted data. Linear search works on anything.


Interview Tips and Practice Problems

Linear search is rarely asked directly, but it is the starting point of many problems. Interviewers often expect you to first describe the simple O(n) scan and then improve it.

Try these problems using a single pass:

  • Find the largest and smallest element in an array

  • Find the second largest element in one pass

  • Check whether an array contains any negative number

  • Find the first non-repeating character in a string (hint: count first, then search)

  • Find the index of the first element greater than a given value

  • Search for a target in a 2D matrix (row by row, like in the 2D Arrays chapter)

A useful habit: whenever your solution has a linear search inside another loop, ask yourself, "Can I avoid repeating this scan?" That question leads to better algorithms.


The Main Idea

Linear Search checks elements one by one until it finds the target or reaches the end.

Start
  ↓
Compare current element with target
  ↓
Equal?  → Yes → return index
  ↓ No
Move to next element
  ↓
End of array? → return -1

The facts to remember:

Best case    → O(1)
Average case → O(n)
Worst case   → O(n)
Space        → O(1)
Sorted data needed? → No

Linear search is simple, works on any data in any order, and costs O(n) time. When the data is sorted, a much faster approach exists — and that is exactly what we will learn next with Binary Search.