Practice question · Multiple choice
Binary search is far faster than linear search but is used less often in practice. Why is it used less often than its speed would suggest?
Hints
- Ask what has to be true before binary search can start.
- Compare the cost of sorting once with the cost of one scan.
Show the answer
B. It requires the data to be sorted, which costs more
Why
The precondition is the cost. Sorting is and a scan is , so for one lookup the scan wins, binary search pays off across repeated queries.
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…
- Order the steps of merge sort on [3, 1, 4, 2].
- Binary search finds a name among 1,000 sorted entries in ~10 steps. Estimate the steps needed for…