Question: Our existing binary search algorithm (Chapter 3, Example 13) contains the pseudocode instruction find the index k midway between i and j after which the target x is compared to the list item at index k, the "midpoint 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).