The binary search calculator gives the worst-case and average number of comparisons needed to find an item in a sorted list, and compares them with a linear scan.
How the calculation works
- Enter the number of sorted items.
- Enter the time of one comparison.
- The calculator gives the worst-case steps, the average steps, the linear scan average, the times and the speed-up.
Example
For 1,000,000 sorted items, a binary search needs at most ⌈log2(1,000,001)⌉ = 20 comparisons and about 18.93 on average. A linear scan needs 500,000 on average. At 50 ns per comparison the binary search takes 1.000 µs and the scan 25.00 ms, which is about 26,411 times as many comparisons.
Why it matters
The calculator helps programming students, developers and interview candidates to see why logarithmic search scales so well and to estimate lookup times in sorted arrays and indexes.
Good to know
The same halving idea applies to guessing games, bisection in debugging, such as finding which commit broke a build, and root finding. To find the number of guesses needed to identify a number from 1 to 100, enter 100 and read 7 as the worst case. Note that on real hardware, the time per comparison is not constant: the first steps hit memory that is cached, while the last ones on a huge array can miss the cache, so measured times are larger than the simple estimate. For data on disk, a tree with wide nodes, such as a B-tree, does the work in fewer reads. A hash table gives constant average time but does not keep the order.
Related tools
The hash collision calculator covers hash tables, the page table size calculator shows another logarithmic structure, the roofline model calculator relates data movement to speed and the logarithm calculators compute log2 directly.