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 such that A[i]-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 sa 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 1. If left > right return "no solution" 2. it Rand(left right) 3. If Alil - k return i 4. If A[i] k return RandomBinarySearch(A,k,left, i-1) 5. If A[i]k RandomBinarySearch(A,k,i+-1,right) In this question, we will figure out the expected running time of this RandomBinarySearch. Note that all the work done by the algorithm consists of comparing some Ali to k (and then recursing and comparing some other Ali to k). In particular, each Ali] is compared to k either 0 or 1 times. The expected running time is thus the expected number of comparisons made by the algorithm. 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 such that A[i]-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 sa 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 1. If left > right return "no solution" 2. it Rand(left right) 3. If Alil - k return i 4. If A[i] k return RandomBinarySearch(A,k,left, i-1) 5. If A[i]k RandomBinarySearch(A,k,i+-1,right) In this question, we will figure out the expected running time of this RandomBinarySearch. Note that all the work done by the algorithm consists of comparing some Ali to k (and then recursing and comparing some other Ali to k). In particular, each Ali] is compared to k either 0 or 1 times. The expected running time is thus the expected number of comparisons made by the algorithm