One works on anything. The other is ten times faster — but has a catch.
The Search Problem
Searching is one of the most fundamental operations in computing. Given a collection of n items, find whether a target value exists — and if so, where.
Two algorithms dominate for searching in arrays:
- Linear Search — simple, general, O(n)
- Binary Search — fast, but requires sorting, O(log n)
Choosing between them isn't just about speed — it's about understanding the structure of your data and the trade-offs involved.
Linear Search
How It Works
Linear search (also called sequential search) is the simplest possible approach: scan every element from left to right until you find the target or exhaust the array.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Return index if found
return -1 # Return -1 if not found
Step-by-Step Example
Array: [15, 3, 42, 8, 27, 6], Target: 27
Check arr[0] = 15 → Not 27, continue
Check arr[1] = 3 → Not 27, continue
Check arr[2] = 42 → Not 27, continue
Check arr[3] = 8 → Not 27, continue
Check arr[4] = 27 → Found! Return 4
5 comparisons to find an element at index 4.
Complexity
| Case | Comparisons | Time Complexity |
|---|---|---|
| Best case | 1 (target is first) | O(1) |
| Worst case | n (not found) | O(n) |
| Average case | n/2 | O(n) |
When to Use Linear Search
- The array is unsorted (binary search won't work).
- The array is small (overhead of sorting isn't worth it).
- You're searching once — sorting first only helps if you'll search many times.
- The data structure doesn't support random access (e.g., linked lists).
- You need to find all occurrences (not just the first).
Advantages
- Works on any array — sorted, unsorted, doesn't matter.
- Works on any data structure that can be iterated (linked lists, streams).
- No preprocessing required.
- Very simple to implement and debug.
Disadvantages
- Slow for large arrays — O(n) means doubling the array size doubles the time.
- Not suitable for high-frequency lookups in large datasets.
Binary Search
How It Works
Binary search only works on a sorted array. It repeatedly halves the search space by comparing the target to the middle element:
- Look at the middle element.
- If it equals the target → done.
- If the target is smaller → search the left half.
- If the target is larger → search the right half.
- Repeat with the remaining half.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Found
elif arr[mid] < target:
low = mid + 1 # Target in right half
else:
high = mid - 1 # Target in left half
return -1 # Not found
Step-by-Step Example
Sorted array: [3, 6, 8, 15, 27, 42], Target: 27
Step 1: low=0, high=5, mid=2 → arr[2]=8 < 27 → search right half
Step 2: low=3, high=5, mid=4 → arr[4]=27 = 27 → Found! Return 4
Only 2 comparisons instead of 5 with linear search!
The Magic of Halving
Each step cuts the remaining search space in half. Starting with n elements:
After 1 step: n/2 elements remain
After 2 steps: n/4 elements remain
After 3 steps: n/8 elements remain
After k steps: n/2^k elements remain
We stop when n/2^k = 1, so k = log₂(n).
For n = 1,000,000 elements:
- Linear search: up to 1,000,000 comparisons
- Binary search: at most 20 comparisons (log₂(1,000,000) ≈ 20)
Complexity
| Case | Comparisons | Time Complexity |
|---|---|---|
| Best case | 1 (target is middle) | O(1) |
| Worst case | log₂(n) + 1 | O(log n) |
| Average case | log₂(n) | O(log n) |
Recursive Implementation
Binary search can also be written recursively:
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1 # Base case: not found
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return binary_search_recursive(arr, target, low, mid - 1)
The recursive version is cleaner but uses O(log n) stack space. The iterative version uses O(1) space.
A Common Bug: Integer Overflow
In languages with fixed-size integers (like Java or C):
// WRONG — can overflow if low + high > Integer.MAX_VALUE
int mid = (low + high) / 2;
// CORRECT
int mid = low + (high - low) / 2;
Python doesn't have this issue (integers are arbitrary precision), but it's worth knowing for interviews.
Side-by-Side Comparison
| Property | Linear Search | Binary Search |
|---|---|---|
| Requirement | None | Array must be sorted |
| Best case | O(1) | O(1) |
| Worst case | O(n) | O(log n) |
| Space complexity | O(1) | O(1) iterative, O(log n) recursive |
| Works on linked lists? | Yes | No (no random access) |
| Works on unsorted data? | Yes | No |
| Simple to implement? | Yes | Moderate |
| Preprocessing needed? | No | Sort first: O(n log n) |
When Does Sorting + Binary Search Beat Linear Search?
Suppose you have an unsorted array of n elements, and you'll perform k searches.
- Linear search for k queries: O(k × n)
- Sort once + binary search for k queries: O(n log n) + O(k × log n)
Sort + binary search wins when:
k × n > n log n + k × log n
k(n - log n) > n log n
k > n log n / (n - log n) ≈ log n (for large n)
Even just log n searches (about 20 for a million elements) makes sorting first worthwhile. In practice, if you're going to search more than once, sort your data.
Variations of Binary Search
Binary search is powerful and generalizable. Common variations:
Find the first occurrence
def first_occurrence(arr, target):
low, high, result = 0, len(arr) - 1, -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid
high = mid - 1 # Keep searching left
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
Find the last occurrence
Same idea, but keep searching right: low = mid + 1 when found.
Binary search on answer
Many optimization problems can be solved with binary search on the answer space, not the data. If you can check "is X feasible?" in O(n) time, binary searching over all possible X values gives O(n log n) total.
Summary
- Linear search scans sequentially — O(n), works on any array, no preprocessing.
- Binary search halves the search space — O(log n), but requires a sorted array.
- The difference is dramatic at scale: binary search makes ~20 comparisons where linear makes 1,000,000.
- If you search once in an unsorted array: use linear search.
- If you search many times: sort first, then use binary search.
- Binary search extends beyond arrays: it applies to any monotone function over an ordered domain.
Next post: Linked Lists — the dynamic, pointer-based alternative to arrays.
Top comments (0)