Hong Life CalculatorsUnderstanding the binary search and comparison count calculator — concept and principle
How many comparisons does it take to find an item or to sort a list? This calculator answers that for n items: the worst case of binary search on sorted data, the average of a plain linear scan, the theoretical minimum for any comparison-based sort, and the exact worst case of merge sort. It shows why sorting once and searching many times pays off.
How it is calculated
- Binary search, worst case: ⌊log₂ n⌋ + 1 comparisons.
- Linear search, average: (n + 1) ÷ 2, assuming the target is present and equally likely to be anywhere.
- Sorting lower bound: log₂(n!), computed with the log-gamma function because n! itself is far too large.
- Merge sort, worst case: n·⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1, which is close to n log₂ n − n + 1.
The principle
Each comparison in binary search halves the remaining range, so after j comparisons at most n ÷ 2ʲ candidates are left; the search ends once that drops below one, after about log₂ n steps. The sorting bound is an information argument: a sort must distinguish all n! possible orders, and each yes/no comparison can at best halve the possibilities, so at least log₂(n!) comparisons are needed in the worst case. By Stirling's formula log₂(n!) ≈ n log₂ n − 1.443n, which is why no comparison sort can beat Θ(n log n). Merge sort comes within a few percent of this bound.
Worked example
- Input: n = 1,000,000.
- Binary search: log₂ 10⁶ ≈ 19.93, ⌊19.93⌋ + 1 = 20 comparisons.
- Linear search: (1,000,000 + 1) ÷ 2 = 500,000.5 comparisons on average.
- Lower bound: log₂(1,000,000!) ≈ 18,488,884.82.
- Merge sort: ⌈log₂ 10⁶⌉ = 20, so 10⁶ × 20 − 2²⁰ + 1 = 20,000,000 − 1,048,576 + 1 = 18,951,425.
| Number of items | Worst-case comparisons (binary search) |
|---|---|
| 250,000 | 18 |
| 500,000 | 19 |
| 750,000 | 20 |
| 1e+06 | 20 |
| 1.25e+06 | 21 |
| 1.5e+06 | 21 |
| 2e+06 | 21 |
How to read the result
Binary search is about 25,000 times cheaper than a linear scan here, but it needs sorted data. Sorting costs roughly 19 million comparisons, so if you will search the same data fewer than a few dozen times, a linear scan may be cheaper overall. Merge sort's worst case is only about 2.5% above the lower bound, so there is little room left to improve comparison counts.
Common mistakes
- Running binary search on unsorted data, which silently gives wrong answers.
- Computing the midpoint as (low + high) ÷ 2 with fixed-size integers, which can overflow; use low + (high − low) ÷ 2.
- Assuming the lower bound applies to every sort: counting sort and radix sort do not compare elements and can run in linear time.
Frequently asked questions
Why is it ⌊log₂ n⌋ + 1 and not log₂ n?
The count must be a whole number, and the last comparison is needed even when one candidate remains. For n = 1,000,000 that gives 20.
How many steps for a billion items?
Only 30, because 2³⁰ is just over a billion.
Is a hash table faster than binary search?
On average, yes: a lookup takes a constant number of probes, but a hash table cannot answer range or nearest-value queries.
Sources: D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley (binary search; minimum-comparison sorting) · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (lower bounds for sorting)