Practice question · Multiple choice
Binary search on a million sorted items needs about 20 comparisons; a linear scan needs up to a million. Why is the sorted-ness worth so much?
Hints
- After comparing with the middle element of sorted data, what do you know about the other halves?
- Ask what a comparison in unsorted data rules out.
Show the answer
A. Because order lets one comparison eliminate half the candidates
Why
One comparison against sorted data eliminates half a million candidates; the same comparison in unsorted data eliminates one. Order is stored information, and binary search is the mechanism that spends it, which is why building an index is worth O(n log n) when the queries are many.
Practise Searching Strategies
The app has 7 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.