Binary Search
Scenario
A NoSQL database uses LSM Trees to flush data to disk as immutable, sorted files (SSTables) with millions of records. A linear scan would take seconds per query, destroying throughput.
How does the database instantly locate a specific record on disk without scanning?
Why it exists
Problem: O(N) linear scanning is too slow for massive datasets. Searching a billion records takes a billion operations.
Naive approach: Keep data in a Hash Map. But Hash Maps cannot perform range queries or find the 'next largest' element, and they use significant memory overhead.
Better idea: If the array is strictly sorted, checking the middle element allows you to mathematically eliminate half of the remaining array instantly. This 'decrease and conquer' approach drops the search time to O(log N).
Mental model
Looking up a word in a physical dictionary. You don't read page by page. You open to the middle; if your word is alphabetically earlier, you discard the right half of the book and repeat.
Maintain two pointers, `low` and `high`, defining the active search space. Calculate the `mid` index. If `arr[mid] == target`, you are done. If `arr[mid] < target`, the target must be to the right, so update `low = mid + 1`. If `arr[mid] > target`, update `high = mid - 1`. Repeat until `low > high`.
Repeated decision: Compare `arr[mid]` to the target. Discard the half where the target mathematically cannot exist.
Explanation
Binary search is the quintessential O(log N) algorithm. Every comparison halves the search space. Searching a billion records requires at most ~30 comparisons.
The loop invariant is rigid: if the target value exists anywhere within the original array, its index is strictly bounded within the inclusive interval `[low, high]`.
A critical engineering detail is the calculation of the midpoint. The mathematical formula `mid = (low + high) / 2` is flawed. In languages with fixed-size integers (C++, Java), if `low` and `high` are near the 32-bit limit, their sum overflows, wrapping around to a negative number and causing a segmentation fault. The overflow-safe formula is `mid = low + (high - low) / 2`.
Binary search is foundational to highly scaled systems. Databases perform binary search on disk-based SSTables. Network routers use hardware-optimized binary searches on routing tables for Longest Prefix Match (LPM) IP lookups.
Key points
- O(log N) Time: Halves the search space on every iteration. Vastly faster than O(N) for large datasets.
- Requires Sorted Data: The elimination logic relies on the strict monotonicity (sorted order) of the data.
- Overflow-Safe Midpoint: Always use `mid = low + (high - low) / 2` to prevent integer overflow.
Pattern: Decrease and Conquer
Recognition cues:
- The input array is explicitly stated to be sorted.
- The problem requires an O(log N) time complexity.
Failure signals
- You are using binary search on an unsorted array. The logic completely breaks down.
- You used `(low + high) / 2` and failed hidden test cases due to integer overflow.
Engineering examples
Database Storage (LSM Trees)
Quickly finding records in massive, immutable SSTable files on disk.
Because SSTables are pre-sorted, binary search locates records directly on disk blocks without linear scanning.
Git Bisect
Isolating the single commit that introduced a bug out of 10,000 commits.
By testing the midpoint commit and flagging it 'good' or 'bad', git bisect discards half the history graph per step, finding the bug in ~13 steps.
When not to use
- Data is frequently inserted or deleted: Maintaining a sorted array for binary search requires O(N) time for insertions/deletions. If data changes constantly, a Balanced Binary Search Tree (O(log N) inserts/searches) is better.
Common mistakes
- Integer Overflow on Midpoint: Using `(low + high) / 2` causes integer overflow on large arrays. Always use `low + (high - low) / 2`.
- Infinite Loops (Off-by-One): Failing to aggressively update `low = mid + 1` or `high = mid - 1`. If you write `low = mid`, the pointers may never cross, causing an infinite loop.
Glossary
- loop invariant
- A condition or rule that must always remain true while a loop is running.
- segmentation fault
- A crash that happens when a program tries to access memory it shouldn't.
- strict monotonicity
- A sequence where each value is completely guaranteed to be larger or smaller than the previous one.
Recall questions
- Why is `mid = (low + high) / 2` considered a bug in languages like Java and C++?
- What is the overflow-safe formula for calculating the midpoint?
- What is the loop invariant for binary search?
Questions & answers
Implement a standard binary search to find a target in a sorted array.
Set `low = 0, high = len - 1`. While `low <= high`, calculate safe `mid`. If `arr[mid] == target`, return `mid`. If `< target`, `low = mid + 1`. If `> target`, `high = mid - 1`.
Approach: Standard Binary Search.
Find the peak element in an array where elements increase then decrease.
Use binary search. Compare `arr[mid]` to `arr[mid+1]`. If it's greater, the peak is to the left (including mid), so `high = mid`. Otherwise, the peak is to the right, so `low = mid + 1`.
Approach: Binary search on unsorted (but conditionally monotonic) array.
Interesting facts
- Jon Bentley, in his book 'Programming Pearls', noted that while the first binary search was published in 1946, the first published binary search without bugs (handling integer overflow) didn't appear until 1962.
Continue learning
Previous: Linear Search
Next: Lower Bound
Next: Upper Bound
Next: Binary Search on the Answer
Related: Lower Bound
Related: Binary Search on the Answer