Skip to content
Omnikalc

Binary search steps calculator

Enter the number of sorted items and the time of one comparison to get the worst-case and average number of steps of a binary search and the speed-up over a linear scan.

Updated on
Your inputs

Value out of range

ns

Value out of range

Results

Worst-case comparisons

20

Average comparisons for a successful search
18.93
Average comparisons for a linear scan
500,001
Time of a binary search (worst case)
1.000 µs
Time of a linear scan (average)
25.00 ms
Speed-up in comparisons
26,411 ×

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.

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.

Frequently asked questions

How many steps does a binary search need?

Each comparison halves the range of candidates, so the worst case is ⌈log2(n + 1)⌉ comparisons. For 1 million items that is 20, and for 1 billion it is only 30. The count grows by one every time the list doubles.

What is the average case?

For a successful search where every item is equally likely, the average is about log2(n) − 1 comparisons, a little less than the worst case, since half of the items sit at the deepest level. An unsuccessful search takes about the worst-case number.

When is a linear scan better?

For very short lists, below about 10 to 20 items, a linear scan can be as fast or faster because of simpler code and cache behavior. The list must also be sorted, and sorting costs n log n, so it only pays off when you search many times.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.