Practice question · Numerical answer
A sorted list holds 64 items. Binary search halves the range at each comparison. In the worst case, how many halvings are needed to reduce it to one item?
Hints
- Ask what power of 2 equals 64.
- 64, 32, 16, 8, 4, 2, 1, count the arrows.
Show the answer
6
Why
, so six halvings. Linear search on the same list could need 64 comparisons, the same data, an order of magnitude apart, purely from exploiting the ordering.
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 1,048,576 items, which is 2 to the power 20. How many halvings does binary search need to…
- Order the steps of merge sort on a list.
- Sort each situation by the search method it calls for.