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 Alf] 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 1. If left > right return "no solution" 2. i -Rand(left....right) 3. If Ali] = k return i 4. If Ali] > k return RandomBinarySearch(A,k,left, i-1) 5. If Ali] right return "no solution" 2. i -Rand(left....right) 3. If Ali] = k return i 4. If Ali] > k return RandomBinarySearch(A,k,left, i-1) 5. If Ali]