Question 1

If a binary search was used on the list in the accompanying figure, which element would the search element be compared to first?

Accepted Answer

In a binary search, the middle element is compared first. In this case, the middle element is 35.

Question 2

If the list in the accompanying figure was to be searched for the number 44 using a binary search, how many key comparisons would have to be made?

Accepted Answer

In a binary search, the list is repeatedly divided in half. Assuming the list is sorted, it takes log2(n) comparisons to find an element. For a list of 32 elements, it would take at most 5 comparisons.

Question 3

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?

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.

Question 4

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?

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.

Question 5

Suppose that L is a sorted list of length 1000. To determine whether an item is in L, the maximum number of comparisons executed by the binary search algorithm, as discussed in this book, is ____.

Accepted Answer

The answer of Suppose that L is a sorted list...

Question 6

Which technique does a binary search use to find an element in a list?

Accepted Answer

A binary search uses the divide and conquer technique to find an element in a list. It repeatedly divides the list in half and checks if the element being searched for is in the first half or the second half, until the element is found or the list is exhausted. This technique reduces the search time significantly as compared to a linear search.

Question 7

If the list in the accompanying figure were to be searched using a sequential search on an ordered list, how many key comparisons would be made to find the number 44?

Accepted Answer

Sequential search on an ordered list starts from the beginning of the list and compares the search key with each element until the search key is found or the end of the list is reached. 
For finding 44 in the given list, the search will proceed as follows:

1. Compare 44 with 21, 44>21, so move to the next element. 
2. Compare 44 with 25, 44>25, so move to the next element. 
3. Compare 44 with 30, 44>30, so move to the next element. 
4. Compare 44 with 32, 44>32, so move to the next element. 
5. Compare 44 with 35, 44>35, so move to the next element. 
6. Compare 44 with 40, 44>40, so move to the next element. 
7. Compare 44 with 42, 44>42, so move to the next element. 
8. Compare 44 with 44, found the key, and stop the search.

So a total of 5 key comparisons are made to find the number 44.

Question 8

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. What are the values of first and last when the while loop, in the body of the binarySearch method, terminates?

Accepted Answer

Binary search starts with the whole list and repeatedly divides the search interval in half. If the search value is less than the item in the middle of the interval, it narrows the interval to the lower half, otherwise to the upper half. For the given list and search value of 110, the search would narrow down to the interval between indexes 7 (value 120) and 6 (value 100), where first (the start of the search interval) becomes 7 and last (the end of the search interval) becomes 6, indicating that the value 110 is not in the list and the search interval is empty.

Question 9

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?

Accepted Answer

Binary search starts with the whole list and repeatedly divides the search interval in half. For the given list, the initial values of first and last are 0 and 8 (indices of the first and last elements). The search for 28 will narrow down to the segment where 28 is actually located. When the search terminates, both first and last will point to the index of 28, which is 3, making the correct answer first = 3, last = 3.

Question 10

What is the maximum number of key comparisons made when searching a list L of length n for an item using a binary search?

Accepted Answer

The maximum number of key comparisons in a binary search is given by the formula $2 \log_2 n + 1$, which is approximately $2 \log_2 n + 2$ when considering integer values. This accounts for the binary division of the list and the final comparison to find the target.

Quiz 14: Applications of Arrays Searching and Sorting and Strings