COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
How many comparisons would it take to find the value 2 in the following list using a binary search?[1, 4, 7, 8, 5, 2, 9]
|
|
3
|
|
|
2
|
|
|
6
|
|
|
Not possible, list is out of order
|
Explanation:
Detailed explanation-1: -The number of comparisons necessary to get to this point is i where n/2i =1. Solving for i gives us i =log n . The maximum number of comparisons is logarithmic with respect to the number of items in the list. Therefore, the binary search is O(log n) .
Detailed explanation-2: -A binary search of 10, 000 items requires at most 14 comparisons. Thus, in terms of the number of comparisons, binary search is much more efficient than sequential search. However, in order to use the binary search approach, the items must be presorted.
Detailed explanation-3: -Here, we have to apply the binary search on 32 elements. So, it will take log232 = 5 comparisons to search for the element.
There is 1 question to complete.