Linear Search Visualizer

Linear search is the algorithm you would invent yourself in about four seconds: look at each element until you find what you want, or run out of elements. It is the simplest search that exists, and dismissing it as a beginner's exercise misses the two things that make it genuinely interesting.

The first is that it makes no assumptions. Binary search demands sorted data. Hash lookup demands a hash function and a table. Linear search demands nothing at all — it works on any sequence, in any order, over any type with an equality test, including data arriving one item at a time from a source you cannot rewind. The second is that on small arrays it is often the fastest option available, because its access pattern is perfectly sequential and the CPU cache rewards that heavily.

What is linear search?

Linear search — also called sequential search — examines each element of a collection in order, comparing it against the target, and returns as soon as it finds a match. If the sequence is exhausted without a match, the target is not present.

It is the only search that is complete under no preconditions. That phrase does a lot of work. It means you can hand linear search an unsorted array, a linked list, a generator, a file being read line by line, or a network stream, and it will still be correct. Every faster search buys its speed by requiring something of the data first — sorted order, a hash table, an index — and that requirement has a cost that has to be paid somewhere.

For a one-off search on unsorted data, linear search is not merely acceptable; it is optimal. Sorting the array to enable binary search costs O(n log n), which is strictly worse than the O(n) you were trying to avoid. Sorting to search once is always a losing trade.

Why it works

Correctness is close to trivial, which is part of the appeal. The invariant is: before examining index i, the target does not appear anywhere in positions 0 through i−1. It holds at the start vacuously, and each iteration either finds a match — in which case the algorithm returns the right answer — or extends the range of positions known not to contain the target by one.

If the loop finishes, the invariant covers the entire array, which is precisely the statement that the target is absent. There is no cleverness and no edge case: the proof is the loop.

This robustness is why linear search is the fallback in almost every hybrid structure. When a hash table's bucket contains a handful of entries, it linear-searches them. When a B-tree node is small enough, implementations often scan it linearly rather than binary-searching. The simple algorithm keeps turning up inside the sophisticated ones.

Step-by-step walkthrough

Search [13, 9, 21, 15, 39, 19, 27] for 39.

1. Index 0: is 13 equal to 39? No. Move on.
2. Index 1: is 9 equal to 39? No.
3. Index 2: is 21 equal to 39? No.
4. Index 3: is 15 equal to 39? No.
5. Index 4: is 39 equal to 39? Yes — return index 4 after five comparisons.

When linear search actually wins

The comparison with binary search is usually presented as O(n) versus O(log n), which makes linear search look indefensible. In practice there are four situations where it is the right choice.

The data is unsorted and you search once. Sorting costs O(n log n). Searching linearly costs O(n). Sorting to search a single time is strictly worse, no matter how much faster the subsequent search is.

The array is small. Below roughly 10 to 100 elements, depending on the data, linear search beats binary search in wall-clock time despite doing more comparisons. Its access is perfectly sequential, so the CPU prefetcher loads the next elements before they are needed; binary search jumps around and each jump risks a cache miss. It is also branch-predictable, where binary search's midpoint comparison is close to a coin flip and mispredicts constantly.

The data cannot be indexed. Linked lists, streams, generators and files being read forward have no random access, so binary search's midpoint jump is either impossible or costs O(n) to reach. Linear search is the only option.

The match is usually near the front. If your access pattern is skewed — recently-used items, popular products, hot cache entries — the expected number of comparisons can be far below n/2, and self-organising variants exploit this deliberately.

How the animation above works

Each cell is checked in turn, amber while under examination and struck through once ruled out. The eliminated count climbs by exactly one per comparison, which is the visual signature of a linear scan — contrast it with binary search, where a single comparison eliminates half of what remains.

Try searching for a value that is not present. The algorithm has no choice but to examine every element before it can conclude anything, which is why unsuccessful searches always cost the full n comparisons. Then set a target you can see near the front and note how few comparisons it takes. That spread between best and worst case — 1 to n — is the whole story of linear search's performance.

Time complexity

Best case O(1). The target is the first element and one comparison finds it.

Average case O(n). For a successful search over a uniformly random position, the expected number of comparisons is (n+1)/2 — about half the array. The constant of one-half is real and worth remembering, but it does not change the growth class.

Worst case O(n). The target is last, or absent entirely. Note that an unsuccessful search is *always* the worst case: the algorithm cannot conclude absence without inspecting every element.

The practical consequence: linear search is fine for occasional lookups over modest collections and untenable as the core of a hot path. A linear search inside a loop over the same collection is the classic accidental O(n²), and it is one of the most common performance bugs in real code.

Space and variants

O(1) auxiliary space. One loop counter. Nothing is allocated, nothing is copied, and the input is never modified.

Sentinel linear search appends the target to the end of the array, guaranteeing a match and removing the bounds check from the inner loop. The loop condition drops from two tests per iteration to one, which used to matter a great deal and matters less on modern branch-predicting CPUs — but it remains a neat demonstration of trading a precondition for speed.

Self-organising search moves a found element towards the front, either by one position (transpose) or all the way (move-to-front). On skewed access patterns this makes frequently-requested items progressively cheaper to find, and it is the idea behind move-to-front list caches.

Parallel or vectorised search compares several elements per instruction using SIMD. This does not change the O(n) complexity, but it can cut the constant factor by a factor of four to sixteen, and it is how high-performance scanning code is actually written.

Complexity at a glance

The numbers below are what the counters in the visualiser converge on. Raise the array size and watch the comparison count grow at the rate this table predicts.

Pseudo code

Language-agnostic, and close enough to the implementations below that you can read them side by side.

Linear Search in five languages

Working reference implementations — copy or download any of them. They are written to be read, so the comments explain the decisions rather than restating the code.

/**
 * Linear search. Returns the index of the first match, or -1.
 * Works on any array, sorted or not — that is the entire point.
 */
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    // Returning here rather than recording and continuing is what makes the
    // average case n/2 instead of n.
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearch([13, 9, 21, 15, 39, 19, 27], 39)); // 4
console.log(linearSearch([13, 9, 21, 15, 39, 19, 27], 100)); // -1

Advantages and disadvantages

Real-world applications

• Searching small collections — configuration lists, menu options, enum lookups — where the setup cost of anything smarter is not repaid.
• Scanning unsorted data once, such as filtering a log file or finding the first record matching a condition.
• Streaming and generator pipelines, where random access does not exist and binary search cannot be expressed.
• The fallback path inside hash tables, where a bucket holding a few colliding entries is scanned linearly.
• Small nodes inside B-trees and similar structures, where implementations often scan rather than binary-search because it is faster at that size.
• Any search by arbitrary predicate rather than by key, since binary search requires ordering by the thing you are searching for.

Interview questions

The questions that actually get asked about Linear Search, with the answers an interviewer is listening for.

1. Q1. When would you use linear search over binary search?

   When the data is unsorted and you only search once — sorting costs O(n log n), which is worse than the O(n) scan you were avoiding. Also when the collection is small (roughly under 100 elements), where sequential access and branch prediction make it faster in practice; when the data has no random access, such as a linked list or stream; and when searching by an arbitrary predicate rather than by the key the data is ordered on.

2. Q2. What is the average number of comparisons in a successful linear search?

   (n+1)/2, assuming the target is equally likely to be at any position — roughly half the array. An unsuccessful search always costs exactly n comparisons, because absence cannot be concluded without examining everything.

3. Q3. Explain sentinel linear search and what it actually saves.

   You write the target into the last position, which guarantees a match, so the loop no longer needs its bounds check — one comparison per iteration instead of two. It was a meaningful optimisation on older CPUs. On modern hardware with good branch prediction the saving is small, and it requires a mutable array, so it is more valuable as an illustration of trading a precondition for speed than as a technique to reach for.

4. Q4. How would you speed up repeated searches over the same unsorted data?

   Amortise the preparation. Build a hash map once for O(1) average lookups, or sort once and use binary search for O(log n). Both cost O(n) or O(n log n) up front and pay off from the second search onwards. If accesses are skewed towards a few popular items, a move-to-front self-organising list can help without any preprocessing at all.

5. Q5. Why is linear search sometimes faster than binary search on small arrays?

   Cache behaviour and branch prediction. Linear search walks contiguous memory, so the prefetcher has the next elements loaded before they are requested, and the loop branch is highly predictable. Binary search jumps to distant midpoints, risking a cache miss per step, and its comparison is close to a coin flip so the CPU mispredicts constantly. Below roughly 100 elements those effects outweigh the comparison count.

Common mistakes

• Continuing the loop after finding a match instead of returning, which doubles the expected work and returns the last match rather than the first.
• Returning 0 rather than −1 for 'not found', which collides with the legitimate index 0 and produces false positives.
• Using <= in the loop bound, reading one element past the end of the array.
• Comparing with == in JavaScript instead of ===, so "5" matches 5 and the search reports a match that is not one.
• Comparing objects with reference equality when value equality was intended, which silently finds nothing.
• Nesting a linear search inside a loop over the same collection, creating accidental O(n²) behaviour that only shows up at production data sizes.
• Using linear search where the data is already sorted, discarding the ordering that would have enabled O(log n).

Optimisation tips

• Return immediately on a match — the single most important detail, and the easiest to get wrong.
• If lookups are repeated, build a hash map or sort once and binary-search afterwards; the preprocessing pays for itself quickly.
• For skewed access patterns, move found elements towards the front so popular items become progressively cheaper to reach.
• Search backwards when the target is more likely to be recent, such as a log or an append-only history.
• Use built-ins — indexOf, find, std::find — which are often vectorised and always clearer than a hand-written loop.
• Where the workload justifies it, SIMD lets you compare several elements per instruction; the complexity stays O(n) but the constant factor drops sharply.

Summary

Linear search examines each element in turn until it finds the target or exhausts the collection. It is O(n) in the average and worst case, O(1) in the best, and needs no extra memory and no preconditions on the data.

Its value is not speed but universality: it is the only search that works on unsorted arrays, linked lists and streams alike, and it is provably the right choice when you are searching unsorted data once. It also wins outright on small collections, where sequential access and predictable branching beat binary search's superior comparison count. The moment lookups become repeated and the collection grows, switch to a hash map or sort once and use binary search.

Frequently asked questions

Related algorithms

• Binary Search

  Halve a sorted range on every comparison — a million elements in twenty checks.

  O(log n)Beginner

• Bubble Sort

  Repeatedly swap adjacent pairs until the largest values have bubbled to the end.

  O(n²)Beginner

• Breadth-First Search

  Explore a graph level by level with a queue — the shortest path on unweighted edges.

  O(V + E)Intermediate