Practice question · Fill in the blanks
Complete the reason binary search is fast.
Binary search is fast because each comparison ______.
Word bank: removes one element from consideration · removes half of the remaining elements · sorts part of the list · doubles the range being searched
Hints
- Compare with linear search, which eliminates exactly one candidate per comparison.
- That is why the cost is a count of halvings.
Show the answer
Binary search is fast because each comparison removes half of the remaining elements.
Why
Each comparison discards half the remaining candidates, so the number of comparisons is the number of halvings, logarithmic. Linear search eliminates one per comparison, which is why its cost is proportional to n.
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…
- 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…
- 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.