Problem 1: Random Binary Search (20 points total) 1 Consider the Following Problem: Input: a sorted array A of length n, and a target number k Output: index i such that Ali] -k, or no solution if none exists. Previously, we showed that binary search solves this problem in O(log(n)) time by repeatedly looking at the middle and recursing to one side. Let's say that instead of picking the middle element, we picked a random element in the array. Here is the pseudocode. Algorithm: RandomBinarySearch(A,k,left,right) - in the initial call, left - 0 and right -n-1 I. If left right return "no solution" 2. i