You are given two arrays, A and B, each of which contains n integers. The elements in each array are guaranteed to already be in sorted order in the input,

i.e.

A[0] A[1] . . . A[n 1],

and also

B[0] B[1] . . . B[n 1].

Give as fast an algorithm as you can for finding the median value of all the 2n numbers in both A and B. (We define the median of 2n numbers to be the average of the nth smallest and nth largest values.) Argue that your algorithm is correct and give its running time.