CareerCup

geeksforgeeks.org/archives/2105

i have a solution and it's O(logn1+logn2)

We may assume that the median is in the first array .

let n=(n1+n2);
if n is odd{
let k=(n+1)/2
else k=n/2
the element m in position i of the first array is the answer only when there
are ( k-1-(i-1) ) elements smaller than it...
we can use binary search method to find the median...
the solution is O(logn1+logn2)

1. Median of 1st array=m1,and of second array be m2
2.if(m2>m1)
Do a binary search for nearest possible element (m1+m2)/2 in both arrays
O(log n)

1. Median of 1st array=m1,and of second array be m2
2.if(m2>m1)
Do a binary search for nearest possible element (m1+m2)/2 in array 2 and save it. Do binary search again in array 1 and compare with save. update if possible
O(log n)

First Merge two sorted arrays to get a single sorted array.
Time = ( n + m ) -> Consider it as n.. Hence merging takes O(n) time.

Find Median.
Index of the median element = (int) ((n+m)/2) -> Which can be achieved in constant time..

Hence Solution is of the order O(n) ->

1. compare the median m_a, m_b of two array a, b
2. if same return the median
3. if different,
if m_a > m_b
//remove right half of a, or left half of b;
if length of a > length of b
remove left half of b, meanwhile remove left (length of b/2) elements of a
recursive;
if length of b > length of a
....
if m_a < m_b
....