Practice question · Sort into groups
Sort each situation by the search method it calls for.
Groups: Linear search · Binary search
- A stream of readings arriving in no order, checked as it arrives
- A sorted dictionary of a million words
- A sorted array of a billion timestamps, queried constantly
- An unsorted list of 30 names, searched once
Hints
- Binary search is only available when the data are already in order.
- Sorting first is worth it only if you will search many times.
Show the answer
Linear search: An unsorted list of 30 names, searched once, A stream of readings arriving in no order, checked as it arrives
Binary search: A sorted dictionary of a million words, A sorted array of a billion timestamps, queried constantly
Why
Binary search needs sorted data and pays off most when searches are repeated. For an unsorted list searched once, sorting costs more than simply scanning, the trade-off is between the one-off sorting cost and the number of searches.
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…
- 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.