Linear Search
Scan every element until the target is found.
How it works
Linear Search is the most fundamental search algorithm: it inspects each element of the collection one at a time, from first to last, until it either finds the target value or confirms it is absent. Because no structural assumptions are made about the data, it works on any sequence — sorted, unsorted, or partially ordered — without any preprocessing step.
The algorithm's O(1) best case occurs when the target is the very first element. On average it scans n/2 elements, and in the worst case (target absent or at the end) it examines all n elements. Despite its O(n) average complexity, linear search is often the fastest choice for small arrays (typically fewer than 8–16 elements) because modern CPUs prefetch contiguous memory extremely efficiently, and binary search's branching overhead and cache miss cost can dominate on short sequences.
Linear Search also handles duplicate values naturally — it can return the first, last, or all occurrences simply by adjusting termination conditions. Its extreme simplicity makes it a common choice in situations where correctness and readability outweigh raw throughput, such as ad-hoc scripts, test helpers, or searching through configuration lists read once at startup.
Complexity
Visualizer
Where it's used in the real world
Database query engine (table scan)
Finding rows in an unindexed columnWhen a query filter targets a column with no index, the database has no choice but to perform a full sequential scan. For small tables or one-off analytical queries, the overhead of building an index exceeds the cost of a single linear scan, so databases deliberately fall back to this strategy.
JavaScript runtime / V8
Array.prototype.find and indexOf on short arraysV8 uses linear search internally for small typed arrays (length < 8) because the binary search branch penalty and bounds-check overhead cost more cycles than the sequential scan on data that fits entirely in a cache line.
Network packet inspection
Scanning ACL rule lists in small firewall configurationsFirewall ACLs are typically evaluated in order (first-match wins). For deployments with fewer than a dozen rules, linear scan is simpler to reason about than tree or hash structures, and its sequential memory access pattern makes it near-optimal on modern hardware.
Implementation
function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1; // not found
}
// Usage
const data = [14, 3, 27, 9, 45, 6, 31, 18];
console.log(linearSearch(data, 45)); // 4
console.log(linearSearch(data, 99)); // -1