Suppose you have two separate sorted arrays of numbers, A[1 m] and B[1 n], where all the numbers in A and B are distinct. Given an integer k where 1 k m + n, design an algorithm that finds the k^th smallest element in the merge of arrays A and B in O(lg k) time. (Note: Explicitly merging the sorted arrays A and B will take (m + n) time, which is too much. Your algorithm, from the point it receives the unmerged arrays A and B, to the point at which it outputs the k^th smallest element, must run in O(lg k) time.) In your solution, be sure to:

a. present your algorithm using prose and pictures

b. analyze the running time of your algorithm