Consider the problem of searching a sorted array A[1..n] for the leftmost occurrence of a query value x. Binary search is one algorithm for this problem, but is it the fastest possible?

1. How many different outcomes does the search problem have for an array of size n? How did you arrive at this number? (Remember that not found is a valid outcome!)

2. 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] < x?, where x is the query value. How many different outcomes can such a comparison have?

3. Sketch a decision tree for solving this problem in this model on arrays of size 4, using the tree notation. Your tree must exactly match the sequence of comparisons performed by the 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.)

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