Combined median of two sorted arrays in O(logN)

Today one of my friend preparing for google interview asked me this question.

Q. You are given two sorted arrays. Find the median of combined array in O(logN) time.

Here is solution I though of.

Let us say we are given two sorted arrays A and B.

Hint : Think how do we find median if elements are not sorted. Find the smallest one and find the biggest one and remove them from array. Repeat same procedure for rest of the elements.

Here we will use similar strategy. Let s=min(size(A),size(B)). 

If median(A) <  median(B), Then remove s/2 number of elements from beginning of array A and remove same number of elements from end of array B.

If median(B) < median(A), Then remove s/2 number of elements from beginning of array B and remove same number of elements from end of array A.

We will get two new sorted arrays.

Repeat the procedure till any of the array gets finished.

 

Here the trick is to remove same number of elements from both of the arrays in every iteration so finally we end with one sorted array left whose median is wanted answer.