3. (a) You are given a sorted array A[1...n] of keys, and another key r which is stored somewhere in A. Show how to find the index k so that A[k] = x in time 0(1+log k). (Note k is not given, and can be much smaller than n). (b) Same, but now find k in time 0(1 + log(min{k, n k})