linear-search

Scan one element at a time until the key appears.

best: O(1)
average: O(n)
worst: O(n)
space: O(1)

reference implementation

verified source·read-only

loading editor

brief

Linear search walks the array from left to right, comparing each element with the target until it matches or the array ends. It needs no ordering and no preprocessing, so it is the baseline every faster search is measured against: its cost is proportional to how far the target sits from the front.

the math

The scan invariant

Before probe $i$ , no element of $a[0..i-1]$ equals the target.
Each probe either finds the target or extends the scanned prefix by one element.
The invariant needs no ordering — any sequence of values will do.

One probe per element

Each step compares exactly one element with the target.
The probe is the only work: nothing moves, so swaps and writes stay at zero.

Worst case: the target is absent

When the target is not present the scan examines all $n$ elements, then returns $-1$ .
That is the $O(n)$ worst case: doubling the array doubles the number of probes.

Stopping at the first match

The scan stops at the first index whose value equals the target.
Because it returns immediately, the cost is the target's position, not the array length.
A target at the front costs a single probe; the best case is $O(1)$ .

▍ Linear Search · small

requesting trace

· decoding trace

· replaying events

· mounting renderer

0/0

fun facts

Linear search needs no ordering: it works on any sequence, sorted or not.
In the worst case — a missing target — every one of the n elements is probed before the scan gives up.
On a random position the expected cost is about n/2 probes, so the scan is linear on average as well.
A million-element array can need a million linear probes where binary search of ordered data needs at most twenty, which is the price of sorting first.

linear-searchstep 0/00%spaceplay←→steppprojectorrreset