Searching Algorithms
Linear vs binary search — when sorted data pays off
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.
Try it interactively
Binary Search Visualizer
Animated binary search over a sorted array with target input, step controls, speed, live comparison counter and pseudocode. Runs in your browser.
Open toolLinear Search Visualizer
Animated linear search with target input, step controls, speed, live comparison counter and pseudocode. Works on unsorted data. Runs in your browser.
Open toolFrequently asked questions
Why is binary search faster than linear search?
Binary search discards half the remaining elements at every step, so it needs only about log₂(n) comparisons — 20 steps for a million items versus up to a million for linear search. The catch is that the data must be sorted first.
When should I use linear search instead of binary search?
Use linear search when the data is unsorted, very small, or stored in a structure without random access (like a linked list). Sorting just to enable binary search only pays off when you search the same data many times.