Our existing binary search algorithm

Our existing binary search algorithm

Our existing binary search algorithm (Chapter 2, Example 40) contains the pseudocode instruction

find the index k of the middle item in the list L[i ]-L[ j]

after which the target x is compared to the list item at index k, the “middle item.” Suppose that this instruction is replaced by

if i = j then

k =j

else

k-i+ 1

end if

a. Draw the decision tree that results from using the modified algorithm on a sorted list with n = 8.

b. Give the exact number of comparisons required  in the worst case for n = 8.

c. Give a worst-case order-of-magnitude expression for the number of comparisons required as a function of n, and justify your expression. Comment on the use of this algorithm as opposed to the original binary search algorithm, which is Θ(log n).

Is this the question you were looking for? If so, place your order here to get started!