Linear Search - The Sequential Scan Algorithm

Linear Search is the algorithm you already know before you know any algorithms. It is the instinctive approach: start at the beginning, check each element one by one, and stop when you find what you are looking for — or when you run out of elements to check. No tricks, no prerequisites, no ceremony. Just a sequential scan from start to finish.

It is easy to dismiss linear search as a beginner’s algorithm, something you graduate away from once you learn better techniques. But that dismissal is premature. Linear search has real, legitimate use cases, and understanding exactly when it shines — and when it does not — is a mark of a developer who thinks carefully about trade-offs rather than reflexively reaching for the most sophisticated tool.

A Brief History

Linear search is one of the oldest searching algorithms in computing, predating the discipline itself. Long before computers existed, people searched through ordered and unordered lists by hand — scanning receipts, checking ledgers, reading through index cards — using exactly this approach. Sequential scanning is simply the most natural way to search a list when you have no additional structural information about where things are.

When electronic computers emerged in the 1940s and 1950s, linear search was among the very first algorithms implemented. Early programs searching through memory or punched cards operated sequentially almost by necessity; the hardware itself was often sequential. Binary search and hash-based lookup came later, as data structures and memory models grew more sophisticated.

The simplicity that makes linear search feel naïve today is precisely what made it foundational: it requires no sorted order, no hash function, no auxiliary structure, and no preprocessing. You just iterate.

How It Works

The algorithm is straightforward enough to state in plain language without losing any precision:

Start at the first element of the list.
Compare the current element to the target value.
If they match, return the current position (or the element itself). You are done.
If they do not match, advance to the next element.
If there are no more elements to check, the target is not in the list. Return a sentinel value such as -1 or null.

That is the entire algorithm. There are no edge cases hiding in the middle, no tricky off-by-one conditions in a pivot calculation, and no invariants to maintain across recursive calls. The logic fits in your head completely.

A minimal implementation in TypeScript looks like this:

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

Notice what the function does not require: the array does not need to be sorted, the elements do not need to be comparable in any ordered sense (only equality matters), and no setup work is needed before calling it.

Time Complexity

Linear search has a time complexity of $O(n)$ , where $n$ is the number of elements in the list. This is because in the worst case — when the target is the last element, or is not present at all — the algorithm must examine every single element before it can give an answer.

The three cases break down as follows:

Best case: $O(1)$ — The target is the very first element. One comparison, done.
Average case: $O(n)$ — On average, the target is somewhere in the middle of the list, requiring roughly $n/2$ comparisons. Since constants are dropped in Big-O notation, this is still $O(n)$ .
Worst case: $O(n)$ — The target is at the last position, or absent entirely. Every element is examined.

The worst-case cost is the one that matters most in practice, because it is the cost you must budget for in any system that cannot guarantee where the target lives. And $O(n)$ means the runtime grows linearly with the size of the input: double the list size, double the expected scan time.

Compare this to binary search, which achieves $O(\log n)$ by exploiting sorted order, or hash map lookup, which achieves $O(1)$ amortized through a hash function. Those algorithms are strictly faster at scale — but they come with requirements: binary search needs a sorted list, and hash maps need to be built in the first place.

Space Complexity

Linear search has a space complexity of $O(1)$ . It operates entirely in-place, needing only a single loop variable (the index pointer) to track its current position. No additional arrays, no recursion stack, no auxiliary data structure of any kind.

This is a genuine strength. In memory-constrained environments — embedded systems, low-level system code, environments where allocations are expensive — the zero auxiliary space requirement is meaningful. Even in ordinary application code, an algorithm that needs no setup and no teardown has a simplicity advantage that compounds over time.

Advantages and Disadvantages

Advantages

Works on any list. Sorted, unsorted, partially sorted — it does not matter. Linear search makes no assumptions about the order of elements.
No preprocessing required. You can call it immediately on any array, with no build step.
Trivially simple to implement and verify. There is almost nothing to get wrong, which means almost nothing to debug.
$O(1)$ space. No memory overhead beyond the iteration variable.
Handles small datasets efficiently in practice. For short lists, the constant factors of simpler algorithms beat the asymptotic advantage of more complex ones. Cache locality and branch predictor behavior can make a tight loop over a small array faster in wall-clock time than an algorithmically superior but more complex implementation.

Disadvantages

$O(n)$ worst-case time. On large datasets, it does not scale. A million-element list requires up to a million comparisons.
No benefit from sorted order. If your data happens to be sorted, linear search ignores that structure entirely, leaving performance on the table.
Not appropriate for repeated searches on large datasets. If you are searching the same collection thousands of times, the cost of $O(n)$ per query adds up fast. Build a hash map or sort and use binary search.

When to Use Linear Search

This is where most discussions of linear search stop being useful, so let me be concrete.

The list is small. If you are searching through fewer than a few hundred elements, the performance difference between $O(n)$ and $O(\log n)$ is measured in nanoseconds. The overhead of sorting the array or building a hash map will cost more than you ever save. Use linear search, ship the feature, move on.

The data is unsorted and you only need to search once. Sorting an array costs $O(n \log n)$ . If you sort just to do one binary search, you have done more work than a linear scan would have required. The break-even point for sorting-then-binary-searching versus linear-searching is roughly $O(\log n)$ queries — fewer than that, and linear search wins.

The data structure does not support random access. Binary search requires jumping to the middle of a collection, which means $O(1)$ index access. Linked lists, streams, generators, and certain database cursors do not provide that. Linear search works on anything you can iterate.

Simplicity matters more than raw speed. Code that gets deployed is better than code that is perfectly optimized but not written yet. Code that is obviously correct is easier to review, audit, and maintain than code that is subtly clever. If the bottleneck is elsewhere, linear search in a non-critical path is the right call.

You are searching for a condition, not a value. If you need the first element matching some predicate — “the first user with an expired token”, “the first task marked overdue” — you are inherently doing a linear scan, because arbitrary predicates impose no exploitable order. In JavaScript and TypeScript, Array.prototype.find is linear search by another name, and it is the right tool for this job.

The deeper lesson is this: algorithmic complexity is a model of how performance scales with input size, not a ranking of algorithms by absolute quality. An $O(n)$ algorithm on a list of 50 elements runs in microseconds. An $O(\log n)$ algorithm with expensive preprocessing on the same list may run slower in total. Reach for binary search or hash maps when you have large data, frequent queries, and the structural requirements they demand. Reach for linear search when you do not — and do not feel like you are cutting corners when you do.

Sometimes the simplest tool is the right one.