Linear Search vs Binary Search
The classic O(n) vs O(log n) tradeoff — Binary Search is dramatically faster, but only works on sorted data.
A simple method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. It is one of the simplest searching algorithms.
When to use it
Use Linear Search when the data is unsorted, small, or a linked structure where random access isn't possible — it requires no preprocessing.
An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
When to use it
Use Binary Search whenever the data is already sorted (or sorting it once and searching many times is worth the O(n log n) upfront cost) and supports random access, like an array.
Key Differences
- Linear Search works on any collection; Binary Search requires the data to be sorted first.
- Linear Search is O(n); Binary Search is O(log n), a massive difference at scale (1M items: ~1,000,000 vs ~20 comparisons worst case).
- Binary Search needs random access (arrays); it performs poorly on structures like linked lists.
- Linear Search needs no setup; Binary Search only pays off if you search the same sorted data repeatedly.
If your data is sorted (or can be sorted once and queried many times), Binary Search wins by orders of magnitude. Otherwise Linear Search is the only option.