Linear Search Algorithm: The Pattern Behind Every First Attempt

You have an array. You need to find a value. The data is unsorted, you have no index, no binary search, no hash map, no tricks.

So you check the first element. Not it. Second. Nope. Third. Getting warmer? Keep going until you hit what you're looking for or run out of array.

That's it. That's linear search.

Before you close the tab: almost every brute-force solution you write in a coding interview is linear search in disguise. The interviewers who watch you skip it entirely and jump straight to the clever solution? They're not impressed. They're writing "jumped to solution without establishing baseline" in your feedback doc. Knowing when linear search is the right tool, and when it's the bottleneck you need to optimize away, is a real skill.

Check Every Single One, Yes, Every One

Linear search scans a collection from one end to the other, comparing each element against a target. When it finds a match, it stops and returns. When it exhausts the collection, it signals failure.

No sorting required. No preprocessing. No assumptions about the data. It works on literally anything you can iterate over.

Here's what it looks like on a list of names:

["Alice", "Bob", "Charlie", "Dana", "Eve"]
  index 0   1       2          3      4

You're searching for "Charlie." Check index 0 ("Alice"): no. Index 1 ("Bob"): no. Index 2 ("Charlie"): yes, return 2. Done.

If "Charlie" were at index 4, you'd check all five elements. If the name weren't there, you'd check every single one before concluding it's absent. That's the defining property: one by one, in order, no skipping. Brute. Force.

Write the Linear Search Algorithm From Memory

Short enough to fit in a tweet, though that comparison stopped being useful years ago.

def linear_search(arr: list, target) -> int:
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

function linearSearch(arr: unknown[], target: unknown): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

Both return the index if found, -1 if not. Standard contract.

If you need all occurrences instead of just the first, the structure barely changes:

def linear_search_all(arr: list, target) -> list[int]:
    return [i for i, val in enumerate(arr) if val == target]

You collect instead of returning early. One pass, every match captured.

One thing worth knowing: Python's in operator and list.index() are both linear search under the hood. When you write if target in my_list, Python is dutifully checking every element in order. It's not doing anything clever. It's not judging you. But it is O(n), and that matters when the list is large and you're doing it repeatedly inside another loop.

You Pay With Time, Not Memory

Linear search is O(n) in the worst and average case.

Best case: the target is the first element. One comparison, done. O(1). You cannot count on this.

Average case: the target is somewhere in the middle. You check roughly n/2 elements. Big-O drops the constant, so that's still O(n).

Worst case: the target is last, or absent. You check everything. O(n).

n	Comparisons (worst case)
10	10
1,000	1,000
1,000,000	1,000,000

Double the array, double the work. Linear is right there in the name. For more on reasoning about complexity classes, see the Big-O Notation guide.

Space is O(1). You iterate in place, no new arrays, no hash maps, no recursive call stack. The only variables are the loop index and the return value. Many algorithms with better time complexity require O(n) space for preprocessing or O(log n) for a recursion stack. Linear search trades speed for zero memory overhead, which is sometimes exactly what you want.

Nobody Talks About When Linear Search Actually Wins

Linear search looks embarrassingly slow on paper. For large sorted datasets, it is. But there are real situations where it's the correct choice and you will look smart for picking it.

When the data is unsorted. Binary search requires sorted data. If you can't sort, or the cost of sorting dominates your budget, linear search is not a concession. It's the answer.

When the array is small. For arrays under a few dozen elements, the overhead of sorting before searching often costs more than scanning. Constant factors matter at small scales, and Big-O hides them. Sorting a 10-element array to avoid "inefficient" linear search is a performance anti-pattern.

When you need all occurrences. Binary search finds one instance. Then you have to expand left and right to catch duplicates, which starts looking suspiciously like a linear scan anyway. Linear search finds every occurrence naturally in a single pass.

When the data structure doesn't support random access. Linked lists don't give you O(1) index access, so you can't jump to the midpoint efficiently. Binary search on a linked list degrades to O(n log n), strictly worse than a straight scan. For any linked list traversal, whether you're finding the midpoint, the kth node from the end, or detecting a cycle, you're doing linear search by necessity.

When data arrives as a stream. You receive elements one by one and need to find something as you go. There's no other option. You cannot sort a stream.

Sorting First: Is It Worth It?

The decision between linear search and binary search almost always comes down to one question: is the data sorted, and can you afford to sort it?

Sorting costs O(n log n). If you're searching once, sorting before searching makes the total cost O(n log n), versus O(n) for a linear scan. Linear search is cheaper for a single search on unsorted data. Full comparison in the binary vs linear search guide.

If you're running many searches on the same dataset, sorting once and binary searching repeatedly pays off. Sort at O(n log n), then each subsequent search is O(log n) instead of O(n). The breakeven is roughly when the number of searches exceeds log n, which happens fast.

When you can't sort because the data must stay in original order, build a hash map instead. O(n) to build, O(1) per lookup. You spend O(n) extra memory to drop search time from O(n) to O(1). See The Time-Space Tradeoff for when that swap is worth it.

How Linear Search Shows Up in Interviews (Everywhere)

You almost never write a function called linearSearch in an interview. You write the logic without naming it. It is everywhere, hiding inside your solutions like a developer who heard there's free pizza in the conference room.

Brute force starting points. The classic: find two numbers that sum to a target. The brute force checks every pair. That's O(n²), because for each element (one linear scan) you scan the rest (another linear scan). When you say "the brute force is O(n²)," you're describing two nested linear searches. Always say this out loud. Do not skip it.

Finding extremes or first matches. Maximum element, minimum element, first element satisfying a condition. All linear scan. These appear constantly as subproblems inside larger solutions. You don't even notice you're doing them.

Final collection passes. After solving the hard part, one sweep to collect or verify results. Merge intervals, count occurrences, gather valid indices. A linear pass at the end.

Unsorted data constraints. Any time a problem says the array is not sorted, your baseline is linear search. The problem is telling you binary search is off the table.

The brute force you must state out loud. On problems with non-obvious optimal solutions, interviewers want you to start with the linear approach. "The naive solution scans the entire array for each query, giving us O(nq) overall. The bottleneck is the repeated linear scan, which we can eliminate with a hash map." That transition from O(n) scan to O(1) lookup is a pattern that appears constantly.

The trap is treating linear search as too simple to mention. Articulating the brute force clearly, naming the complexity, and identifying why it's insufficient is core problem-solving signal. Jumping to the optimal answer without explaining what you're optimizing against reads as memorized rather than understood.

Practicing this on paper is one thing. Saying it clearly under time pressure is another. Voice-based mock interviews at SpaceComplexity put you through exactly this: walk through the brute force, reason about its cost, pivot to the better approach, all while narrating in real time.

Sentinel Search: A Micro-Optimization Nobody Asked For

One micro-optimization worth knowing, mostly so you can mention it if an interviewer asks about constant-factor tricks.

Place the target value at the very end of the array before you start scanning. Your loop then has one condition per iteration instead of two. You're guaranteed to find the target eventually, so you don't need to check bounds separately.

def sentinel_linear_search(arr: list, target) -> int:
    n = len(arr)
    last = arr[n - 1]
    arr[n - 1] = target

    i = 0
    while arr[i] != target:
        i += 1

    arr[n - 1] = last

    if i < n - 1 or last == target:
        return i
    return -1

This halves the number of comparisons per element in practice. Still O(n) asymptotically, but the constant factor drops. This shows up more in systems programming and embedded contexts than in interviews, but it's a concrete example of constant-factor optimization that interviewers occasionally probe when they want to see whether you can think below the abstraction layer.