Linear Search
Walk the array front to back and compare every element — zero preconditions, zero setup, and unbeatable when the data is small or unsorted.
Hands on Interactive visualization
Implementation Code
export function linearSearch(a: number[], target: number): number {
for (let i = 0; i < a.length; i++) {
if (a[i] === target) return i; // first match wins
}
return -1; // exhausted the array: definitively absent
}Big-O Complexity
Average is n/2 comparisons for a uniformly placed hit and n for a miss — but the constant per comparison is tiny and the access pattern is perfectly cache-friendly.
In production When to use
Below a few dozen elements, a linear scan beats binary search in practice: no branching subtleties, no sort precondition, and the whole array often fits in one or two cache lines.
Searching once through unsorted data is O(n) — sorting first costs O(n log n). Any single lookup over data you will not query again should be a plain scan.
Array.prototype.indexOf and includes in JavaScript, list.index and the in operator on Python lists, and slices.Index in Go are all linear scans under the hood.
Finding the first element matching an arbitrary condition — Array.prototype.find, C++ std::find_if, Rust Iterator::position — is inherently linear because the predicate imposes no order to exploit.
Columnar databases and analytics engines scan compressed column chunks with vectorized (SIMD) linear passes — a predictable sequential read that prefetchers and vector units love.
Linked lists and singly-chained hash buckets have no random access, so linear traversal is the only option — which is exactly why hash chains are kept short.
Trade-offs Strengths & weaknesses
- No preconditions: works on unsorted, heterogeneous, or streaming data.
- O(1) space and trivially correct — hard to get wrong in an interview or in production.
- Sequential access is the friendliest possible pattern for CPU caches and prefetchers.
- Works on structures without random access: linked lists, iterators, streams.
- Supports arbitrary predicates, not just equality on a sorted key.
- Fastest option in absolute terms for small n — often up to tens of elements.
- O(n) per lookup — untenable for repeated queries over large data.
- Ignores any structure the data already has (sortedness, index, hash).
- Miss cost is always the full n comparisons.
- Repeated scans over big arrays evict useful data from cache.
- n lookups over n elements is O(n²) — the classic accidental-quadratic bug.
Intuition Mental model
Checking every box on a shelf
You are looking for one labeled box in a storeroom with no ordering system. The only reliable plan: start at one end and check every box until you find it or run out of shelf.
- Start at the leftmost box — no ordering means no smarter starting point exists.
- Read each label and compare it to the one you want; move right on a mismatch.
- The moment a label matches, stop — that is the best-case O(1) hit at the front.
- Reach the end of the shelf without a match and you know, with certainty, it is not there.
- On average you inspect half the shelf for a hit and the whole shelf for a miss — that is the O(n).
Prep Interview questions
When does linear search beat binary search in practice?
How do you find the first element matching a predicate, and can you do better than O(n)?
What is the sentinel optimization for linear search?
You call list.contains inside a loop over another list. What just happened?
How would you parallelize a linear search over a huge array?
Watch out Common bugs
Returning 0 (a valid index) instead of -1, or null instead of undefined, silently turns misses into hits at index 0. Pick one miss convention and test it explicitly.
indexOf, includes, or list.remove(value) inside a loop is O(n) per call — the outer loop makes it quadratic. Profile-visible only once the data grows.
i <= n instead of i < n reads one element past the end — undefined behavior in C-family languages, a panic in Rust, undefined in JavaScript.
Reference equality instead of value equality (== on Java strings, is on Python objects) makes structurally equal targets invisible to the scan.
One screen Cheat sheet
Scan left to right, compare everything, stop on the first match.
- The only search with zero preconditions — unsorted data, streams, linked lists, predicates.
- Beats binary search on small arrays thanks to sequential, cache-friendly access.
- indexOf / includes / in are linear scans — calling them in a loop is O(n²).
- Miss always costs the full n comparisons.
- Sentinel trick removes the bounds check for one comparison per step.
- For repeated lookups, build a hash set or sort once instead.