Binary Search Comparisons
Calculator
Results
- Worst-case comparisons
- 20
- Exact log₂ N
- 19.931568
- Speedup vs. linear search
- 50,000
Computing results
| Worst-case comparisons | 20 |
| Exact log₂ N | 19.931568 |
| Speedup vs. linear search | 50,000 |
formula-map diagram
- Worst-case comparisons
- 20
- Exact log₂ N
- 19.931568
- Speedup vs. linear search
- 50,000
Computing relationship
Formula
comparisons = ⌈log₂ N⌉= 20
Note
This is a simplified model: it applies the standard computing formula to the numbers you entered and ignores protocol overhead, compression variability, retries, contention and other real-world effects. Size your systems with measured data.
Example: with the default inputs, calculator.technology.worst_case_comparisons is 20.
More in Technology and computing
See all →Frequently asked questions
How many comparisons does a binary search need?+
In the worst case it needs ⌈log₂ N⌉ comparisons, where N is the number of sorted items. The calculator rounds log₂ N up to the next whole number.
What does the exact log₂ N value show?+
It is the unrounded base-2 logarithm of N. The worst-case count is that number rounded up, since you cannot make a fraction of a comparison.
How does binary search compare to linear search here?+
The calculator divides N by the worst-case binary comparisons. That ratio shows roughly how many times fewer comparisons binary search needs than checking every item one by one.
Does the list have to be sorted?+
Yes. The formula assumes the items are already sorted, since binary search halves the remaining range at each step. The calculator does not check this for you.
Is this the average or the worst case?+
It is the worst case, as the field and formula state. A search can finish earlier if the item is found sooner, so the real number of comparisons can be lower.