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. What are the values of first and last when the while loop in the body of the binarySearch method terminates?
A) first = 3, last = 3
B) first = 0, last = 3
C) first = 2, last = 4
D) None of these

Question

Quizplus · Accepted Answer

In a binary search, the list is divided in half repeatedly. For the list given, the middle element is 45 (index 4). Since 28 is less than 45, the search continues in the left half. The new middle element is 11 (index 1). Since 28 is greater than 11, the search continues in the right half of this sublist. The new middle element is 25 (index 2). Since 28 is greater than 25, the search continues in the right half of this sublist, which is just the element 28 (index 3). The search finds 28, so first and last both point to index 3 when the loop terminates.

Consider the Following List