## Microsoft Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

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. 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

....

geeksforgeeks.org/archives/2105

- Nithin June 04, 2012