Consider the problem we studied: searching a sorted array A[1..n] for the leftmost occurrence of a query value x. Recall that the binary search algorithm solves this problem and returns the index of the element in the array if it is present, or not found if it is not present. Binary search is one algorithm for this problem, but is it the fastest possible?

PROVIDED PSEUDOCODE:

14. How many different outcomes does the search problem have for an array of size n? How did you arrive at this number?

15. As for sorting, we will use the comparison model of computation, but this time the only comparisons permitted are of the form is A[i]

16. Sketch a decision tree for solving this problem in this model on arrays of size 4, using the tree notation shown in the example from Lecture 6. Your tree must exactly match the sequence of comparisons performed by the (corrected!) binary search code. Include only comparisons of A[i] against x for some i. (You can treat = as another permitted comparison when building your tree.)

17. Using similar decision-tree reasoning to what we used for sort, derive an asymptotic lower bound on the cost of any algorithm for searching a sorted array in the comparison model. Justify your answer.

BSearch (A, n, x) //lower bound upper bound while (L H) md - (L + H)/2 if (A[mid] x) // midpoint -mid + 1 /recur on upper half else recur on lower half if (A[L] = x) //A is a single element return L else return notFound BSearch (A, n, x) //lower bound upper bound while (L H) md - (L + H)/2 if (A[mid] x) // midpoint -mid + 1 /recur on upper half else recur on lower half if (A[L] = x) //A is a single element return L else return notFound