Searching Algorithms

Searching asks a simple question — is this value here, and where? — but the answer’s cost depends entirely on structure.

Linear search

Linear search checks each element in turn until it finds the target or reaches the end. It runs in O(n) and works on any list — sorted or not, array or linked list. For small or unsorted data it is often the right, simplest choice.

Binary search

Binary search repeatedly halves a sorted range: compare the middle element, then discard the half that cannot contain the target. It reaches the answer in O(log n) — about 20 comparisons for a million items versus up to a million for linear search. The catch is the precondition: the data must already be sorted, so binary search pairs naturally with the sorting algorithms above.

The visualizers below show the difference dramatically — linear search crawling element by element, versus binary search leaping to the midpoint and throwing away half the data each step.