Searching
Linear search vs Binary search
Linear search and Binary search both find a value in an array, in different ways. Linear search: scan every element in order. Binary search: halve the range of a sorted array. In the worst case binary search takes O(log n) while linear search takes O(n), so binary search scales better on large inputs.
At a glance
| Property | Linear search | Binary search |
|---|---|---|
| Technique | Scan every element in order | Halve the range of a sorted array |
| Best case time | O(1) | O(1) |
| Average case time | O(n) | O(log n) |
| Worst case time | O(n) | O(log n) |
| Extra space | O(1) | O(1) |
| Stable (equal values keep their order) | Not applicable | Not applicable |
| In place (no extra array) | Not applicable | Not applicable |
| Needs sorted input | No | Yes |
When to choose each
Choose linear search when
the data is unsorted, small, or searched only once.
Avoid it when
you search the same large array many times.
Choose binary search when
the array is sorted and you search it many times.
Avoid it when
the data is unsorted, or cannot be reached by index.
The same inputs, counted
These numbers come from running both real implementations: comparisons, on the sorted array 2, 5, 8, 12, 16, 23, 38.
| Input | Linear search | Binary search |
|---|---|---|
| Target is the first element | 1 | 5 |
| Target in the middle | 4 | 1 |
| Target is the last element | 7 | 5 |
| Target is not in the array | 7 | 6 |