Practice question · Numerical answer
A sorted list holds 1,048,576 items, which is 2 to the power 20. How many halvings does binary search need to narrow it to a single item?
Hints
- The exponent in the power of 2 is the answer.
- Each halving reduces the exponent by exactly one.
Show the answer
20
Why
Twenty halvings. A million items cost 20 comparisons rather than a million, and doubling the data to two million would add just one more.
Practise Searching and Sorting
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Searching and Sorting
- Summing a million floating-point numbers from smallest to largest is more accurate than from largest to…
- Complete the reason binary search is fast.
- Floating-point arithmetic gives 0.1 + 0.2 ≠ 0.3 on essentially every computer. Why does a well-designed…
- A sorted list holds 64 items. Binary search halves the range at each comparison. In the worst case, how many…
- Order the steps of merge sort on a list.
- Sort each situation by the search method it calls for.