# Find median of 2 sorted arrays with different lengths

I'm trying to solve the below problem for my assignment but I have no clue how to find the time algorithm. If I have two arrays of same even length then I get, $T(n) = T(n/2) + \theta(n)$ but what about having $m$ and $n$ (not specified odd or even )?

Let $X[1 .. n]$ and $Y[1 .. m]$ be two arrays, containing n and m numbers respectively and they are already in sorted order. Give an $O(\log n + \log m)$ time algorithm to find the median of all $(n+m)$ elements in arrays $X$ and $Y$.

-

Hint: What you want is to find $p$ such that $X[\frac n2 + p]=Y[\frac m2 -p]$. In the spirit of bisection, start with $p=0$. If $X[\frac n2] \gt Y[\frac m2]$ you need to decrease $p$, while if $X[\frac n2] \lt Y[\frac m2]$ you need to increase $p$.
@newbieLinuxCpp: It works the same. Let's take $X$ to be the numbers $1-100$ and $Y$ to be the numbers $30.1-90.1$ that are $0.1$ more than a multiple of $3$ (so $21$) of them. We check $X[50]=50$ and $Y[11]=60.1$ so we need to move up in $X$ and down in $Y$ by the same number of locations. We will find $X[53]=53, Y[8]=51.1,Y[9]=54.1$, so the median is $53$. You'll have to take larger steps than $1$ to get the $\log(n)$ behavior you want. There are perturbations if you run out of the small array-take the same $X$ and $Y=101,102,103$. – Ross Millikan Jan 29 '13 at 0:50