Searching CS Thinking Example 4
Follow the full solution, then compare it with the other examples linked below.
Example 4
hardA sorted list has 128 elements. In the worst case, about how many comparisons does binary search need, and how does that compare with linear search?
Solution
- 1 Step 1: Binary search repeatedly halves the remaining list, so the worst-case number of comparisons is about `log2(128) = 7`.
- 2 Step 2: Linear search may need to inspect every element, so it can take up to 128 comparisons. That is much slower than 7 for the same list.
Answer
Binary search needs about 7 comparisons, while linear search can need up to 128.
Searching performance depends heavily on the algorithm and the structure of the data. Sorted data enables binary search, which reduces the search space dramatically each step.
About Searching
The process of locating a specific item or value within a collection of data using a systematic strategy. The two fundamental approaches are linear search (check every element one by one) and binary search (repeatedly halve the search space in sorted data).
Learn more about Searching →More Searching Examples
Example 1 medium
Use linear search to find the value 7 in the list [3, 9, 7, 1, 5]. How many comparisons are needed?
Example 2 mediumUse binary search to find 23 in the sorted list [5, 10, 15, 20, 23, 30, 35]. Show each step.
Example 3 mediumCan binary search be used on the unsorted list [8, 2, 5, 1, 9]? Why or why not?