Compare linear and binary search side by side on the same sorted array. Watch how binary search eliminates half the remaining elements each step, dramatically reducing comparisons compared to linear scanning.
| Property | Linear Search | Binary Search |
|---|---|---|
| Time (Best) | O(1) | O(1) |
| Time (Average) | O(n) | O(log n) |
| Time (Worst) | O(n) | O(log n) |
| Space | O(1) | O(1) |
| Requires Sorted? | No | Yes |
| Approach | Sequential scan | Divide & conquer |
Scans every element from left to right until the target is found or the end of the array is reached. Simple but inefficient for large arrays. Works on both sorted and unsorted arrays.
Repeatedly divides the search space in half by comparing the target with the middle element. Requires a sorted array but achieves logarithmic time complexity, making it vastly superior for large datasets.