Consider the Following Problem Input: a sorted array A of length n, and a target numberk Output: index i 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 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