Practice question · Estimate
Binary search finds a name among 1,000 sorted entries in ~10 steps. Estimate the steps needed for 1,000,000,000 (a billion) sorted entries.
Estimate on a scale from 0 steps (0) to 100 steps (100).
Hints
- Each step halves the remainder: the count is .
- A billion ≈ , or reuse the pattern: 1000× more data costs only ~10 more steps.
Show the answer
30 (answers within ±4 count)
Why
About 30 steps, a billion-entry phone book, solved in the time of 30 comparisons. Logarithms barely grow: that is why sorted structures and tree indexes power every database on Earth.
Practise Searching and sorting ideas
The app has 8 more questions on this lesson, and keeps your place in the course. Physics I is free to start.
More questions on Searching and sorting ideas
- Trace selection sort on the list [7, 2, 9, 1]. Order the states the list passes through.
- Classify each sort as O(n²) average or O(n log n) average.
- You guess a number between 1 and 1000; after each guess you learn "higher" or "lower". A smart player needs…
- Binary search is far faster than linear search but is used less often in practice. Why is it used less often…
- Order the steps of merge sort on [3, 1, 4, 2].