Linear Search vs Binary Search — Which Should You Use?
Linear search checks elements one by one until it finds the target. Binary search repeatedly halves a sorted range, discarding half of the remaining candidates with every comparison. The performance gap is enormous — a million elements take up to a million checks linearly but at most 20 binary probes — yet linear search is still everywhere in real code, and for good reasons.
The catch is in that word *sorted*. Binary search does not work at all on unsorted data — not slowly, not approximately, it simply returns wrong answers, because discarding half the array is only valid when order tells you which half the target cannot be in. So the honest comparison is never just O(n) versus O(log n); it is O(n) versus *the cost of having sorted data* plus O(log n).
This page covers when each search wins, how to reason about the sort-cost break-even, and the implementation traps — because binary search is famously one of the easiest algorithms to get subtly wrong.
// quick answer
For a single search over unsorted data, linear search wins outright: scanning is O(n) while sort-then-binary-search is O(n log n) — you would pay more preparing the data than the lookup saves. The break-even comes with repetition. Sort once for O(n log n), and every subsequent query costs O(log n) instead of O(n); after roughly O(log n) searches the sort has paid for itself, and everything beyond that is nearly free. Many lookups over stable data is precisely the regime binary search was made for.
Complexity at a Glance
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
Head-to-Head Differences
| Dimension | Linear Search | Binary Search |
|---|---|---|
| Precondition on the data | None — works on any order, any comparable or even non-comparable equality check | Requires sorted data. On unsorted input it silently returns wrong answers, not slow ones |
| How it eliminates candidates | One element per comparison | Half of the remaining range per comparison — 1,000,000 elements need at most ~20 probes |
| Data structure requirements | Anything iterable: arrays, linked lists, streams, files read once front to back | Needs O(1) random access by index — arrays, not linked lists (jumping to the middle of a list is itself O(n)) |
| Implementation difficulty | Trivial — a loop and an equality check; very hard to get wrong | Notoriously bug-prone: off-by-one bounds, lo <= hi vs lo < hi, midpoint overflow, infinite loops on bad updates |
| Best case / early exit | Target at index 0 → one comparison; on data sorted by access frequency, hot items are found almost instantly | Target at the exact midpoint → one comparison, but average and worst cases are both ~log n regardless |
| Canonical use cases | Small collections, one-off searches, unsorted or constantly changing data, streams, searching by predicate rather than key | Repeated lookups in sorted arrays, database-style indexes, finding insertion points, "search the answer" optimization problems |
| Failure modes | Just slow at scale — a linear scan inside a hot loop turns O(n) code into O(n²) systems | Wrong results on unsorted or stale-sorted data; subtle infinite loops; (lo + hi) / 2 overflow in fixed-width languages |
When to Use Linear Search
- The data is unsorted and you only need to search it once or twice — sorting first would cost O(n log n) to save almost nothing.
- The collection is tiny (say, under ~50 elements) — the loop is simpler and the constant factors make the difference unmeasurable.
- You are searching a linked list, a stream, or anything without random access — binary search cannot jump to the middle.
- You are matching a predicate ("first user whose cart is empty") rather than looking up an ordered key.
- The data changes constantly, so maintaining sorted order would cost more than the searches save.
When to Use Binary Search
- The data is already sorted, or sorted order is cheap to maintain — then every lookup drops from O(n) to O(log n) essentially for free.
- You will perform many searches over the same data: sort once for O(n log n), then answer each query in O(log n).
- You need more than membership: first/last occurrence, insertion point, or nearest value — binary search variants answer all of these.
- You are binary-searching the *answer space* of a monotonic problem (minimum capacity, smallest feasible speed) — a pattern linear scanning cannot touch at scale.
- The collection is large enough that O(n) per lookup is a real cost — thousands of elements and up.
Verdict
For a single search over unsorted data, linear search wins outright: scanning is O(n) while sort-then-binary-search is O(n log n) — you would pay more preparing the data than the lookup saves. The break-even comes with repetition. Sort once for O(n log n), and every subsequent query costs O(log n) instead of O(n); after roughly O(log n) searches the sort has paid for itself, and everything beyond that is nearly free. Many lookups over stable data is precisely the regime binary search was made for.
So the real decision is about your data's lifecycle, not the algorithms' big-O. Ask three questions: Is it sorted (or worth sorting)? Does it support random access? How many times will I search it? Three "yes/many" answers point to binary search; any hard "no" points to linear search — or to a different structure entirely, like a hash table, when you need O(1) lookups without order.
And if you do adopt binary search, respect its reputation: test the boundaries (empty array, one element, target absent, target at both ends), because nearly every binary search bug lives in the last two iterations. Watching the visualizer shrink the lo/hi window step by step is a genuinely good way to build the right mental model before writing your own.
Frequently Asked Questions
Why does binary search require sorted data?
Binary search discards half the array after each comparison, and that is only logically valid if order guarantees the target cannot be in the discarded half. If the middle element is less than the target in a sorted array, everything to its left is also less. On unsorted data that inference fails, so binary search returns wrong answers — not merely slower ones.
Is it worth sorting an array just to binary search it once?
No. Sorting costs O(n log n), which is strictly more than the O(n) of a single linear scan. Sorting pays off only when you amortize it across many searches: after roughly log n queries the sort has paid for itself, and every further lookup costs O(log n) instead of O(n). One-off search on unsorted data: always scan.
Can you binary search a linked list?
Not usefully. Binary search needs O(1) access to the middle element, but reaching the middle of a linked list requires walking half the nodes, which is already O(n). The traversal cost swamps the comparison savings, so a plain linear scan is the practical choice for lists. Skip lists exist precisely to give linked structures logarithmic search.
What are the classic binary search bugs?
Three dominate. Off-by-one boundary updates — writing `hi = mid` where `hi = mid - 1` is needed, causing infinite loops or missed elements. The wrong loop condition — `lo < hi` versus `lo <= hi`, which skips the final one-element range. And midpoint overflow in fixed-width integer languages, avoided by writing `lo + (hi - lo) / 2` instead of `(lo + hi) / 2`.