Binary Search
Runs in browserStep-by-step search patterns
Ready
Basic Search: Standard binary search. Returns any index where the target value is found in the sorted array.
Operation Log
0 eventsWaiting for steps...
Binary Search: The Power of Logarithmic Scaling
In the world of algorithms, efficiency is often the difference between a system that scales to billions of users and one that crashes with only a few thousand. Binary Search is the gold standard for efficiency. By leveraging the fact that data is already sorted, it can find a single needle in a haystack of a billion items in only 30 steps.
1. Visualizing Logarithmic Growth
Binary Search operates in O(log n) time. To appreciate how powerful this is,
compare it to a linear search (O(n)):
| Array Size (n) | Linear Search (Max) | Binary Search (Max) |
|---|---|---|
| 1,024 | 1,024 steps | 10 steps |
| 1,048,576 | 1,048,576 steps | 20 steps |
| 1,073,741,824 | 1,073,741,824 steps | 30 steps |
While a linear search might take seconds or minutes to scan a billion items, Binary Search finishes in microseconds. This is why sorted indexes are the backbone of every modern database.
2. The Hidden Cost: Maintaining Sorted Data
There is no free lunch in computing.
Binary Search requires that the array be sorted. Sorting an unsorted array typically takes
O(n log n) time. If you only plan to search a dataset once,
it is actually more efficient to just use a linear search $(O(n))$.
Binary Search becomes the winning strategy when you have a static or
slow-changing dataset that you need to search thousands of times.
3. Beyond Equality: Leftmost, Rightmost, and Bisect
In real-world data, duplicates are common. A "basic" binary search might return any index of a target value. But often, we need more precision:
- Leftmost / Lower Bound: Finds the first occurrence of a value. This is used when you want to find the start of a range (e.g., "Find all logs starting from 10:00 AM").
- Rightmost / Upper Bound: Finds the last occurrence. Useful for counting duplicates ($Rightmost - Leftmost + 1$).
- Insertion Point: Even if the value doesn't exist, where would it
go? This is exactly how
bisect_leftin Python orstd::lower_boundin C++ work.
4. Real-World Applications: From Git to Databases
Binary Search is ubiquitous in software engineering:
Databases
B-Tree indexes use a form of binary search at each node to quickly navigate millions of rows in SQL and NoSQL databases.
Git Bisect
When a bug is introduced, git bisect uses binary search on your
commit history to find the exact line of code that broke the system.
Network Routing
IP lookup tables use binary search on prefix lengths to route packets across the internet at hardware speeds.
5. Implementation Pitfalls & The Overflow Bug
"Nearly all binary searches are broken."
For 20 years, the standard way to calculate the midpoint was mid = (low + high) / 2.
However, in systems with large arrays, low + high can exceed the maximum value
for a 32-bit integer, causing an overflow and returning a negative index.
The safe version is: mid = low + (high - low) / 2.
Another common error is the infinite loop, usually caused by
incorrectly updating the boundaries (e.g., using low = mid instead
of low = mid + 1).