Binary Search vs Linear Search
Binary Search and Linear Search are both searching. Play them side by side below, then see exactly where they diverge.
Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.
Binary Search
Full topicCompare with the middle of a sorted array and half of it stops mattering.
MIDDLE -> COMPARE -> DISCARD HALF -> REPEAT. Discarded cells recede, the active range contracts.
Linear Search
Full topicCheck every slot in order. On average half the array, in the worst case all of it.
One pointer, one comparison per cell. No assumption about order.
How they differ
Linear search asks nothing of the array and checks each slot in order, so it is O(n) on average and in the worst case. Binary search needs the array sorted, and in exchange every comparison with the middle rules out half of what is left, so it takes O(log n). On an unsorted array only linear search applies. On a sorted array of a million values it is the difference between up to a million comparisons and about twenty.
The run shown here takes 6 steps for Binary Search and 6 steps for Linear Search (Linear search, found). That count moves with the input - use the example tabs above either player to see it change.
| Cost | Binary Search | Linear Search |
|---|---|---|
| best | O(1) | O(1) |
| average | O(log n) | O(n) |
| worst | O(log n) | O(n) |
| space | O(1) | O(1) |