Seven of the other ten entries in Searching buy their speed by assuming something about the data up front — sortedness, at minimum, and sometimes a known length or a known distribution too. Feed any of them unsorted data and they don't fail loudly; they just quietly return wrong answers, because the whole mechanism (bisection, an uneven golden-ratio split, striding forward by a fixed block, a rotation-aware bisection around one break point) depends on order that isn't actually there. An eighth, Saddleback Search, needs the same kind of order, just spread across two axes of a matrix instead of one array. Linear search assumes nothing. It checks each element in turn until it finds the target or runs out of elements, correct on shuffled data exactly as it is on sorted data, in exchange for giving up every one of those eight entries' sub-O(n) guarantees. That makes it the right default exactly when sortedness doesn't hold, or isn't worth establishing for a single lookup — and it has one genuinely underrated optimization of its own, checked below with real counted comparisons rather than taken on faith. (The other two, Quickselect and Binary Search on Answer, don't need sortedness either, but each answers a different question entirely — which rank an element holds, and where a monotonic feasibility check switches from "no" to "yes" — not whether a target exists.)
The array below is deliberately unsorted — 15 elements in an arbitrary order — because that's the one case none of this site's other Searching entries can handle correctly. Pick a preset or edit the array and target directly, then step through. The "assume sorted" checkbox reproduces a real, common bug: applying a sorted-array early-break to data that was never actually sorted.
There's no invariant to prove wrong the way bisection needs one — the loop simply checks every
element in the order it appears. By the time it has examined all n of them without a
match, it has directly ruled out every possible location, so "not found" is exactly as certain as a
match would have been. That's also why it needs no assumption about order: ruling out one element
says nothing about any other, unlike binary search's bisection, where a single comparison discards
an entire half based on the sorted-order guarantee.
A textbook naive loop pays two comparisons per element examined: i < arr.length
to check the loop hasn't run off the end, then arr[i] === target to check the value
itself. The sentinel trick removes the first one entirely. Temporarily append the
target itself to the end of the array, then loop with no bounds check at all — the loop is now
mathematically guaranteed to terminate, because even if the real target isn't anywhere in the
original data, it will always find the copy it just planted:
function linearSearchSentinel(arr, target) {
const n = arr.length;
arr.push(target); // temporary sentinel — guarantees the loop below terminates
let i = 0;
while (arr[i] !== target) i++;
arr.pop(); // restore the original array
return i === n ? -1 : i; // landing on the sentinel itself means "not found"
}Every iteration now costs exactly one comparison instead of two. Simulated against a real naive implementation (bounds check counted as a real comparison, not assumed free) across every array size from 1 to 50 and every possible target index, the ratio holds exactly 2:1 whenever the target is present — not "roughly half," genuinely half every single time, because both versions do the same amount of useful work (one equality check per element up to and including the match) and the naive version's only extra cost is the bounds check paid alongside each one. On this page's own 15-element array:
| target (index) | 17 (1) | 34 (7) | 5 (13) | 49 (14, last) | 100 (absent) |
|---|---|---|---|---|---|
| naive comparisons | 4 | 16 | 28 | 30 | 31 |
| sentinel comparisons | 2 | 8 | 14 | 15 | 16 |
The absent case is close but not quite exact — 2n+1 for naive against
n+1 for sentinel, a ratio that approaches 2 as n grows but is never
precisely 2 for any finite n (31 against 16 above, not 31 against 15.5). The exact-half
claim is specifically about the found case; worth stating precisely rather than rounding both cases
to the same "about half" the way it'd be tempting to.
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1;
}Porting a sorted-array early-break onto unsorted data is a silent, verified bug — try the
"assume sorted" checkbox above against this page's own array and target 5. A common
optimization on sorted data is to stop the scan the moment arr[i] > target,
since nothing sorted-and-later could still be a match. On this page's unsorted array, target
5 genuinely sits at index 13 — but index 0 holds
42, which is already greater than 5. The early-break "optimization" stops
at the very first element and reports "not found," silently wrong, with no error of any kind — worse
even than a slow correct answer, since it never gets anywhere near the real index. The checkbox above
reproduces this exact failure live: uncheck it and the correct scan finds index 13 after 14
comparisons; check it and the same array, same target, comes back not-found after just 1.
The sentinel trick needs a mutable array it can temporarily own, not just read.
It works by pushing a value onto the real array and popping it back off, invisible to a
single-threaded caller — but that's unsafe on an array another reader might observe mid-search (a
concurrent reader could see the extra element), and impossible outright on a fixed-length array
(a typed array like Int32Array has no push) or a read-only source. Any of
those would need a defensive copy first, and that copy alone costs a full linear pass over the array
— the same order of work as the entire search, at which point the optimization is competing with the
very cost it was trying to avoid, not saving anything net.
O(n) worst case and average case (uniformly over target position, or when the
target is absent), O(1) best case (target is the first element checked). This is
provably the best any comparison-based search can do on unstructured data: an adversary
argument shows why — for any algorithm that decides to skip examining some element before checking
it, an adversary could have hidden the target exactly there, so nothing sub-O(n) can be
made worst-case correct without more structure (sortedness, a hash, an index) than "an unordered
list" provides. Every other entry in Searching buys its faster bound by
requiring exactly that extra structure. See Choosing a Search Algorithm for how it fits
alongside the site's other ten Searching entries.