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 110 is in list. Exactly how many key comparisons are executed by binary search?
A) 3
B) 5
C) 8
D) 12

Question

Quizplus · Accepted Answer

Binary search starts by comparing the target value to the middle element of the list. If the target value is less than the middle element, the search continues in the first half of the list. If the target value is greater than the middle element, the search continues in the second half of the list. This process is repeated until the target value is found or the list is exhausted. In this case, the target value is 110 and the list is {5, 11, 25, 28, 45, 78, 100, 120, 125}. The middle element of the list is 45. Since 110 is greater than 45, the search continues in the second half of the list. The middle element of the second half of the list is 100. Since 110 is greater than 100, the search continues in the second half of the second half of the list. The middle element of the second half of the second half of the list is 120. Since 110 is less than 120, the search continues in the first half of the second half of the second half of the list. The middle element of the first half of the second half of the second half of the list is 110. Since 110 is equal to the middle element, the search is complete. Therefore, binary search executes 8 key comparisons to determine whether 110 is in the list.

Consider the Following List