Question 1

-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

In a sequential search on an ordered list, each element is checked one by one from the beginning. If the list is ordered and starts with numbers less than 44, it will take 5 comparisons to reach and find the number 44.

Question 2

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 answer of What is the maximum number of key...

Question 3

-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 typically takes log2(n) comparisons, where n is the number of elements. For a list of 32 elements, it would take at most 5 comparisons.

Question 4

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 5

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

The answer of Consider the following list. list = {5,...

Question 6

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

Accepted Answer

Binary search uses the divide and conquer technique by repeatedly dividing the list in half to locate the target element.

Question 7

-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

The answer of 
-If a binary search was used on...

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 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

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.

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 110 is in list. Exactly how many key comparisons are executed by binary search?

Accepted Answer

Binary search repeatedly halves the search space by comparing the target value to the middle element of the current search space. In this case, 110 is not in the list, so binary search will execute 3 comparisons to determine this.

Question 10

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

In binary search, the middle element is compared with the target. If the target is not found, the search space is halved. For 110, the search will narrow down to indices 6 and 7, and when 110 is not found, 'first' becomes 7 and 'last' becomes 6, terminating the loop.

Quiz 14: Searching and Sorting