Searching

How linear search works

Walk the array front to back, comparing each element with the target. Nothing clever — and that is its virtue: it works on unsorted data, on linked lists, on streams you can only read once. When the data has no structure to exploit, this is the answer, and it is optimal: you cannot verify absence without looking at everything.

The interview point is knowing when to abandon it. The moment the interviewer says the array is sorted, they are inviting you to do better — every probe here eliminates exactly one element, while binary search eliminates half. Watch the probe counter and compare the same target on the binary search tab.

Also worth saying out loud: for a single lookup, sorting first (O(n log n)) to enable binary search is a loss. Binary search pays off when you search the same data many times.

space play / pause · ←→ step