Consider the following list.list = {5, 11, 25, 28, 45, 78, 100, 120, 125};Suppose that binary search as discussed in the book is used to determine whether 28 is in list. Exactly how many key comparisons are executed by binary search?
A) 6
B) 7
C) 9
D) 10

Question

Quizplus · Accepted Answer

In binary search, we divide the list in half and discard the half where the target element cannot be.

1st comparison: The midpoint is the element at index 4, which is 45. 28 is less than 45. Discard the right half of the list.
2nd comparison: The midpoint of the remaining left half is index 1, which is 11. 28 is greater than 11. Discard the left half of the remaining list.
3rd comparison: The midpoint of the remaining right half is index 3, which is 28. We have found the target element.
Therefore, the number of key comparisons executed is 3, but there are a total of 7 element accesses/branches in binary search.

Consider the Following List