How Linear Search Works

Say you're looking for your friend's name in a stack of unsorted business cards. There's only one honest way to do it: pick up the first card, check it, put it down, pick up the next one, check it, and keep going until you either find the name or run out of cards. No shortcuts, no assumptions about order — just checking everything, one at a time. That's Linear Search, and despite being the simplest algorithm in this entire series, it's also the one you'll reach for most often in real code without even realizing it.

How Linear Search Works

1. Start at the first element of the array.
2. Compare it to the value you're looking for.
3. If it matches, you're done — return its position.
4. If not, move to the next element and repeat.
5. If you reach the end without a match, the value isn't in the array.

Walking Through an Example

Search for 23 in [8, 15, 4, 23, 42, 16]:

• Check index 0: 8 → no match
• Check index 1: 15 → no match
• Check index 2: 4 → no match
• Check index 3: 23 → match! Return index 3

Notice there was no assumption that the array was sorted — Linear Search works on any array, in any order. That flexibility is exactly its strength, and exactly its weakness.

Java Implementation

public class LinearSearch {
    public 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[] arr = {8, 15, 4, 23, 42, 16};
        System.out.println(linearSearch(arr, 23)); // Output: 3
        System.out.println(linearSearch(arr, 99)); // Output: -1
    }
}

📝 Note

This is the same "check every element" idea from Day 2's O(n) example — Linear Search isn't a new concept, it's that exact pattern applied to a concrete problem.

Time Complexity

⚠️ Complexity Breakdown

Best case: O(1) — the target is the very first element.
Average case: O(n)
Worst case: O(n) — the target is last, or missing entirely.
Space: O(1) — no extra memory needed.

When Linear Search is Actually the Right Choice

It's tempting to think "O(n) is slow, always use something faster" — but Linear Search wins in specific, common situations:

• The data isn't sorted, and sorting it first would cost more than just searching once
• The array is small enough that the difference is meaningless
• You're only searching once — the cost of sorting first (O(n log n)) isn't worth it for a single lookup

This is why Java's ArrayList.contains() uses linear search internally — for small or unsorted collections, it's genuinely the simplest correct tool for the job.

Common Interview Questions

• Why can't you use Binary Search directly on an unsorted array?
• What's the best-case time complexity of Linear Search, and when does it happen?
• How would you modify Linear Search to find all occurrences of a value instead of just the first one?

The Takeaway

Linear Search is the baseline every other searching algorithm in this series gets compared against. It's never the fastest option when your data is sorted — but it's the most flexible, and understanding exactly why it's O(n) sets up the next post perfectly: Binary Search, which gets the same job done in O(log n) by taking advantage of one extra piece of information — a sorted array.

➡️ Next in the Series

Binary Search: Finding Anything in Logarithmic Time

Happy learning!
— Team CodeElevateX 🚀