Consider the Following Problem: Input: a sorted array A of length n, and a target number k 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 e 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. Rand(left....right) 3. If Alik returni 4. If Ai>k . return RandomBinarySearch(A,k,left, i-1) 5. If Ali right return "no solution" 2. Rand(left....right) 3. If Alik returni 4. If Ai>k . return RandomBinarySearch(A,k,left, i-1) 5. If Ali