Searching CS Thinking Example 3
Follow the full solution, then compare it with the other examples linked below.
Example 3
mediumCan binary search be used on the unsorted list [8, 2, 5, 1, 9]? Why or why not?
Solution
- 1 Step 1: Binary search requires the list to be sorted so it can eliminate half the elements based on comparison with the middle.
- 2 Step 2: On an unsorted list, comparing with the middle element gives no information about which half to search. Linear search must be used instead.
Answer
No. Binary search requires a sorted list. Use linear search for unsorted data.
The power of binary search comes from the sorted order — knowing whether the target is larger or smaller than the middle element tells us which half to discard.
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 4 hardA sorted list has 128 elements. In the worst case, about how many comparisons does binary search nee