Consider the problem we studied in Studio 5: searching a sorted array Aln for the leftmost occurrence of a query value r. Binary search is one algorithm for this problem, but is it the fastest possible? 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!) 14. 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, where z is the query value. How many different outcomes can such a comparison have? 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 at the end of Studio 5, Part B. Include only compar- isons of Ali against 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 Consider the problem we studied in Studio 5: searching a sorted array Aln for the leftmost occurrence of a query value r. Binary search is one algorithm for this problem, but is it the fastest possible? 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!) 14. 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, where z is the query value. How many different outcomes can such a comparison have? 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 at the end of Studio 5, Part B. Include only compar- isons of Ali against 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