Binary search
Look at the middle element. If the target is smaller, everything from the middle rightwards can be discarded without being examined; if larger, everything leftwards. Either way the remaining range is half what it was, so after k probes the range is n divided by 2 to the k, and the search ends when that reaches one. The number of probes is therefore the number of times n can be halved, which is its logarithm base two.
The claim being tested
O(log n)
When it is the right choice
Whenever the data is already sorted and will be searched more than once or twice. The cost of sorting it first is O(n log n), so a single search is cheaper done linearly; a thousand searches are not. The exact crossover is a constant-factor question this tool deliberately cannot answer, which is worth knowing about the tool as well as about the algorithm.
How it works
- Keep a range, starting as the whole list.
- Probe the middle of the range and compare it with the target.
- Discard the half that cannot contain the target.
- Stop when the range is empty; the number of probes is what is counted.
Worth noticing
- On log-log axes this curve bends. That is not noise and not a bad fit: a logarithm is not a power law, so it has no fixed exponent, and its log-log gradient falls towards zero as n grows. It is straight on a log x axis against a *linear* y axis, which is how this page opens.
- The count goes up by exactly one for every doubling of n. From 8 to 131,072 — fourteen doublings and four decades of input — it goes from 4 probes to 18. That sentence is the whole of what O(log n) buys.
- The formulation counted here does one comparison per halving and never stops early on a hit, so the count is exactly ⌈log₂(n+1)⌉ on every input of a given size. A version that returns as soon as it lands on the target would measure how lucky the target was rather than how the algorithm grows.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Extra space
- O(1)
- n is
- the length of a list of numbers
- Measures
- sorted: up to n = 131,072
The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.
A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.