Binary Search Step Counter
Calculate the maximum and average comparisons binary search needs for any sorted array size.
Enter n and see how O(log n) performs versus linear search.
Binary search is one of the most efficient algorithms for finding a value in a sorted list. Instead of scanning from the first element, it repeatedly cuts the search space in half.
The algorithm starts at the middle element. If the target is smaller, it discards the upper half. If larger, it discards the lower half. Each comparison eliminates half the remaining candidates.
Maximum comparisons (worst case): floor(log2(n)) + 1
For a list of 1,000 items, binary search needs at most 10 comparisons. A linear scan needs up to 1,000. For a million items, binary search tops out at 20 comparisons. Linear search needs up to 1,000,000. This is what O(log n) means in practice.
Average comparisons: approximately log2(n) - 1 for large n.
Why it requires a sorted list. Binary search only works because it can make a definitive decision at each step: the target is either in the left half or the right half. Without sorted order, discarding half the list could eliminate the answer.
Practical limits. For very small n (under 8 or so), linear search is often faster because of CPU cache behavior. The list fits in a single cache line and there is no branching overhead. Most language standard libraries switch to linear scan for small subarrays for this reason.
Number of doublings. How many times can n be halved before reaching 1? That is exactly the number of comparisons in the worst case. It is also why adding more data has such little effect on binary search. You need to double the array size just to add one more step.