How many probes does binary search need worst case on a billion sorted entries, and on a trillion?
answer
- each probe removes half the candidates
- how many halvings until one remains?
- anchor on two to the tenth
- floor of the base-2 log, plus one
- a thousandfold more data, ten more probes
basics
~20 sAbout 30 probes for a billion entries and about 40 for a trillion: the worst case is floor(log2 n) + 1. Multiplying the data by a thousand adds only ten probes, because log2(1000) is roughly 10.
solid answer
~50 sWorst case is `floor(log2(n)) + 1` probes. For a billion that is 30, for a trillion 40 — and I can get there without a calculator because 2^10 is about a thousand, so 2^30 is about a billion and 2^40 about a trillion. The useful reflex is the ratio, not the absolute number: multiplying the input by 1000 costs about 10 extra probes, and merely doubling it costs exactly one. The `+1` shows up because the last probe inspects a range that already holds a single candidate; equivalently the bound is `ceil(log2(n + 1))`, the number of yes/no answers needed to separate `n` positions plus the not-found outcome. Two things I would not claim: that logarithmic means constant — it grows without bound, only slowly — and that 30 probes are automatically cheap, since on data that large each probe is likely a distant, uncached access.
go deeper
Memorise the anchor: two to the tenth is about a thousand, so a million takes about twenty probes and a billion about thirty. Be able to produce those numbers without hesitating or reaching for a calculator.
Explain where the count comes from — halving until one candidate remains, plus the final look — and why the logarithm's base is dropped in the big-O label but matters when you quote an actual probe count.
Separate probe count from probe cost. Show you know that thirty scattered accesses over data larger than memory behave very differently from thirty accesses inside a cache-resident range, and what that implies about layout.
Be ready to argue capacity: what a logarithmic access path means for a latency budget as data grows an order of magnitude, and when the real constraint is the per-probe access cost rather than the count.
## The exact bound For a search over `n` ordered candidates, the worst-case number of probes is `floor(log2(n)) + 1`, equivalently `ceil(log2(n + 1))`. Both expressions agree for every positive `n`, and either is a fine thing to say out loud. The second one carries the better intuition: a probe returns a branch decision, the search must be able to distinguish `n + 1` different outcomes (each of the `n` positions, plus "not present"), and each two-way decision can at best halve the set of outcomes still in play. You therefore need at least `log2(n + 1)` decisions, rounded up. Binary search hits that bound, which is why it is not merely *a* good ordered search but an optimal one under comparison-based probing. ## Doing it in your head The only fact you need is `2^10 = 1024`, roughly a thousand. Everything else is multiplication of exponents: | candidates | nearest power of two | worst-case probes | |---|---|---| | 1,000 | 2^10 | 10 | | 1,000,000 | 2^20 | 20 | | 1,000,000,000 | 2^30 | 30 | | 1,000,000,000,000 | 2^40 | 40 | So a sorted directory of every human alive is about 33 probes; one entry per grain of sand on a beach is still under 60. When an interviewer asks "and if the directory grows a thousandfold?", the answer is "ten more probes", and it should arrive instantly. The two ratios worth memorising: **doubling the input adds exactly one probe**; **multiplying it by a thousand adds about ten**. Both fall straight out of the logarithm turning multiplication into addition. ## Why the base does not appear in the big-O label The cost is written `O(log n)` with no base, which sometimes reads as sloppiness. It is not: logarithms in different bases differ by a constant factor (`log2(n) = log10(n) / log10(2)`, about `3.32 * log10(n)`), and big-O deliberately discards constant factors. When you want an actual probe count rather than a growth class, use base 2, because the algorithm's branching factor is two. Quoting `log10` by accident is a classic slip — it turns 30 probes for a billion into 9, and an interviewer will notice. ## What "logarithmic" does and does not promise It does **not** mean constant. The count grows without bound; it just grows so slowly that on any input you can physically store it stays under about 60. Saying "log n is basically O(1)" is a direction-of-claim error, and it collapses distinctions that matter — for instance, that a genuinely constant-time lookup does not care about `n` at all, while a logarithmic one still pays for every thousandfold of growth. It also does not promise the search is *fast* in wall-clock terms. The bound counts probes, and a probe's price is not fixed. Over a small range that fits in fast memory, 30 probes are nothing. Over a billion entries spread across memory or storage, the access pattern is the opposite of sequential: each probe lands far from the last, so most of them miss every level of cache and a few may be storage reads. Thirty scattered accesses can lose to a sequential scan of a much smaller range — which is exactly why practical searches over huge ordered data are usually built on layouts that make each step touch a whole block of neighbours rather than a single lonely position. Keep the two questions separate: *how many probes* is the algorithmic bound, *how expensive is one probe* is a property of where the data lives. ## The worst case, and what triggers it The full `floor(log2(n)) + 1` is reached when the target is **absent** — the range must shrink to nothing before the algorithm may answer "not found". A present target can finish earlier, in the extreme on the very first probe. The average for a present, uniformly-chosen target is only about one probe less than the worst case, though, because the overwhelming majority of positions are only reachable near the bottom of the halving tree: half of all positions are found on the last possible probe. This is worth saying out loud, because it explains why nobody bothers optimising binary search for the lucky case — there is barely any lucky case to exploit. ## Answering the follow-up cleanly A good spoken answer has four beats: quote the closed form, anchor it on `2^10 ≈ 1000`, give the number for the size asked about, then give the *rate* — what doubling and what a thousandfold cost. Adding the caveat that probe count is not probe cost is what separates a memorised figure from someone who has thought about searching data larger than memory.
- Where does the +1 in floor(log2(n)) + 1 come from?From the final probe on a range that already holds exactly one candidate — halving describes how the range shrinks, but the last remaining position still has to be looked at. The equivalent form `ceil(log2(n + 1))` makes the same point differently: the search must separate `n` positions plus the not-found answer, so it needs that many two-way decisions.
- An interviewer says logarithmic growth is basically constant at real sizes. How do you push back?It grows without bound — it just grows slowly. A truly constant-time lookup is indifferent to size; a logarithmic one still pays about ten more probes per thousandfold. And at large sizes the probes themselves get more expensive, because each one lands far from the previous and misses cache, so the cost curve is worse than the probe count alone suggests.
- For a present target chosen uniformly at random, is the average probe count much better than the worst case?Barely — about one probe less. Half of all positions are only resolved on the deepest possible probe and a quarter on the one before it, so the average sits just under the worst case. That is why binary search is never tuned for the lucky early hit: there is almost no lucky case to exploit.
Each probe is one yes/no answer, and yes/no answers are bits. Thirty bits are enough to name any one of a billion things, which is why thirty probes are enough to find one.
saying these in an interview costs you the question
- Treats O(log n) as effectively constant time
- Says a thousandfold more data means a thousandfold more probes
- Quotes log2 of a billion as about nine
- Forgets the absent target is the worst case
- Assumes thirty probes are automatically cheap