Linear Search vs Binary Search
Use binary search when the data is already sorted or you can sort it once and query it many times. Use a linear scan on unsorted data, on short arrays, and whenever you would pay more to sort than the searching saves.
A linear scan costs n comparisons and asks nothing of the data. Binary search costs about log n and asks for order, which is the whole trade. For a million elements that is a million comparisons against twenty, so the question is never which is faster in the abstract but whether you can afford the order it requires.
Side by side
| Dimension | Linear search | Binary search |
|---|---|---|
| Requires sorted input | No | Yes, or some monotonic property |
| Comparisons | n in the worst case | About log2 n, so 20 for a million |
| One-off search on unsorted data | O(n), the right answer | O(n log n) to sort first, then O(log n) |
| Many searches | O(n) each time | Sort once, then O(log n) each |
| Works on | Arrays, lists, streams, anything iterable | Random access only, so arrays rather than linked lists |
| Typical bug | Off-by-one at the ends | Infinite loop from a window that stops shrinking |
When to pick each
Linear search
- The data is unsorted and you need one answer, where sorting costs more than the scan.
- The array is small, and small is bigger than people expect: a scan of 50 elements beats the branch mispredictions of a binary search.
- You are looking for something a comparison cannot order, such as the first element matching an unrelated predicate.
Binary search
- The input arrives sorted, which problem statements say far more often than candidates notice.
- You will search the same data repeatedly, so one sort pays for every later query.
- The search space is not an array at all but a range of possible answers with a yes-or-no test that flips once, which is binary searching the answer.
Sorting an array so you can binary search it once. The sort costs O(n log n), the scan you avoided cost O(n), and the total is now worse than the thing you were optimising. Sorting pays off only across repeated queries, or when the sort buys you something else as well, like the two-pointer structure that a sorted array makes available.
Questions people ask
Is Arrays.binarySearch enough?
For an exact match on a sorted array, yes, and its return value is more useful than it looks: a negative result encodes where the value would belong as -(insertion point) - 1. Interviews still ask for the loop, because the interesting variants are boundary searches rather than exact matches, and those need the predicate form.
What does binary searching the answer mean?
Searching a range of candidate answers rather than an array of data. For a question like the smallest ship capacity that clears the backlog in D days, you binary search capacities and run a feasibility check on each one. It works because the check is monotonic: every capacity below some threshold fails and every one above it succeeds.
Why is binary search on a linked list a bad idea?
Because finding the middle costs a walk. Binary search needs O(1) access to the midpoint, and a linked list only offers O(n) traversal, so each halving costs what the scan would have cost. Sorted data in a structure without random access wants a skip list or a balanced tree instead.