Practice question · Put in order
Order the 'invest structure to buy speed' workflow the lesson describes for searching a fixed dataset many times.
- For each query, jump to the middle of the sorted data
- Answer each search in about log n comparisons
- Halve the range with each comparison
- Sort the dataset once, at a cost of about n log n
Hints
- The one-time cost is paid before any of the fast searches.
- Sorting first is what makes every later search logarithmic.
Show the answer
- Sort the dataset once, at a cost of about n log n
- For each query, jump to the middle of the sorted data
- Halve the range with each comparison
- Answer each search in about log n comparisons
Why
Pay the one-time n log n sort, then every subsequent search is O(log n) instead of O(n). If you search many times, that sort pays for itself, structure bought once, speed gained repeatedly.
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.