Binary Search vs Linear Search
Binary search vs linear search explained with Big O, code, and why binary search needs sorted data first.
Linear search checks every element one by one and works on any data. Binary search repeatedly cuts the search space in half, which is far faster, but only works if the data is already sorted.
Binary Search vs Linear Search at a glance
| Binary Search | Linear Search | |
|---|---|---|
| Time complexity | O(log n) | O(n) |
| Requires sorted data | Yes | No |
| How it works | Repeatedly halves the search range | Checks each element from the start |
| Best for | Large sorted datasets | Small or unsorted datasets |
| Space complexity | O(1) iterative, O(log n) recursive | O(1) |
| Example | Looking up a word in a dictionary | Scanning a shuffled deck of cards for one card |
When to use each
Choose Binary Search when
- Your data is already sorted, or you can afford to sort it once and search it many times.
- The dataset is large enough that O(n) scanning would be too slow.
- You need consistently fast lookups, like in a search feature.
Choose Linear Search when
- The data is unsorted and sorting it first is not worth the cost.
- The dataset is small enough that the difference does not matter.
- You only need to search once, so sorting first would add unnecessary work.
Why binary search is so much faster
Linear search has no shortcuts. To find a value, it checks index 0, then index 1, and so on until it either finds the value or runs out of elements. Binary search takes advantage of sorted data. It checks the middle element, and because the data is sorted, it instantly knows whether the target is in the left half or the right half, throwing away the other half completely. It repeats this halving until it finds the value.
# linear search: O(n)
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
# binary search: O(log n), requires sorted arr
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1A common trap question is asking you to binary search an unsorted array. The honest answer is that binary search simply does not work on unsorted data, since it relies entirely on being able to eliminate half the remaining elements based on order.
Frequently asked questions
Why is binary search O(log n)?
Because each comparison cuts the remaining search space in half. Starting from n elements, you can only halve the range about log base 2 of n times before you are down to one element.
Is it worth sorting data just to binary search it once?
Usually not. Sorting typically costs O(n log n), so if you are only searching once, a single O(n) linear search is cheaper overall than sorting first and then binary searching.
Can binary search be written recursively?
Yes, both iterative and recursive versions are common. The iterative version is usually preferred in interviews since it avoids extra stack frames and the risk of a stack overflow on very large inputs.
Want more interview ready comparisons?
Browse every Binary Search vs Linear Search style breakdown, or explore the full question library.
All comparisons Browse questions