Linear search is the simplest search algorithm — and often the most misunderstood. People assume it is always bad because of its O(n) worst case, but it is the only correct choice in several very common situations.
The animation cycles through four searches on the same unsorted array. Three targets exist in the array and are found at different positions, showing how the cost varies depending on where the value sits. The fourth target does not exist, so the search scans every single element before giving up — that is the worst case O(n).
Watch how eliminated elements fade as the scan pointer moves right. Each step is one comparison — that is your unit of work. The scan progress bar at the top shows what fraction of the array has been ruled out.
Linear search works on any collection — unsorted arrays, linked lists, streams of data arriving in real time. Unlike binary search, it never requires the data to be sorted first.
If the target happens to be the first element, the search returns immediately after one comparison. Expected case on a random array is O(n/2) — on average you find the target halfway through.
If the target is the last element, or is not present at all, every element must be checked. For n = 1,000,000 elements, that is up to one million comparisons.
Every other search algorithm is measured against linear search. Binary search is O(log n) — but only after paying the cost of sorting. For a single search on unsorted data, linear search is optimal.
TIPWatch the scan progress bar fill up as elements are eliminated. When the target is near the start, it fills only a sliver. When the target is not present, it fills completely — that full bar represents your worst case O(n) cost.