Unsorted Arrays vs Binary Search
1. What is the value of the base-2 logarithm of 512, i.e. ?
2. Around 18 teams made it to the final round of a basketball championship. If the team leaders' names are arranged in ascending order and binary search is applied, what is the maximum number of iterations needed to find a particular team leader?
3. For a standard binary search on a sorted array of length , what is the worst-case order of the number of iterations needed to determine that an element is not present?
4. In the best case, if we perform an optimized linear search on a sorted array of length , how many iterations are needed to determine that a searched value is not present when the value is smaller than the first element?
5. In an unsorted array, why can a standard linear search require comparisons in the worst case?
6. Consider the unsorted array . Using linear search from left to right, how many elements must be examined to find the value 8?
7. Suppose an unsorted array contains elements and a value is known to occur somewhere in the array. What is the worst-case time complexity of finding its position using linear search?
8. An unsorted array is searched for a value using linear search. If the value is found at the first position, what is the time complexity of the search in the best case?
9. Why can binary search be faster than linear search on a sorted array?