Understanding how binary search achieves logarithmic time complexity through divide and conquer
Binary search is an efficient algorithm for finding an item in a sorted array. It works by repeatedly dividing the search space in half, eliminating half of the remaining elements at each step.
Key Requirements:
Think of it like searching for a word in a dictionary - you don't start from page 1. Instead, you open to the middle, see if your word comes before or after, and eliminate half the book. Repeat until found!
Compare the target value with the middle element of the array.
If the target is smaller, search the left half. If larger, search the right half. You've eliminated half the elements!
Repeat the process on the remaining half until you find the element or determine it doesn't exist.
Binary search only works on sorted arrays. If the array isn't sorted, you must sort it first (O(n log n)) or use linear search (O(n)).
Code Example:
// Binary search implementation
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}At each step, binary search eliminates half of the remaining elements. This is the key to its efficiency!
The number of steps needed grows logarithmically with the array size:
Linear search (O(n)) vs Binary search (O(log n)):
One-time search: If you only need to search once, linear search (O(n)) is better than sorting (O(n log n)) + binary search (O(log n)).
Multiple searches: If you need to search many times, sort once (O(n log n)) then use binary search (O(log n) per search). After k searches, total cost: O(n log n + k log n). For k > n, this is better than k linear searches (O(kn)).
| Algorithm | Time Complexity | Requirements |
|---|---|---|
| Linear Search | O(n) | No requirements |
| Binary Search | O(log n) | Array must be sorted |
| Hash Map Lookup | O(1) | Hash map must be built first |
| Operation | Binary Search | Linear Search | Explanation |
|---|---|---|---|
| Search (sorted) | O(log n) | O(n) | Binary search eliminates half at each step |
| Search (unsorted) | N/A | O(n) | Must use linear search or sort first |
| Worst Case | O(log n) | O(n) | Binary search always O(log n), linear search worst case O(n) |
When looking up a word in a dictionary, you don't start from page 1. You open to the middle, see if your word comes before or after, and eliminate half the book. This is exactly binary search!
Databases use binary search on sorted indexes to quickly find records. This is why indexed columns are so much faster for queries!
When inserting a new high score into a sorted leaderboard, binary search finds the correct position quickly, even with thousands of scores.
Binary search can find the first/last occurrence of a value, or find all values in a range. Useful for time-series data, logs, and sorted datasets.
For large datasets, binary search is much faster than linear search
The array must be sorted for binary search to work correctly
Eliminates half the search space at each step, leading to logarithmic time complexity
If you need to search many times, sort once then use binary search for each query