Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
I'm sorry but I don't understand what you mean? Correct me if I understood wrong. So, I find the median of both arrays and then compare if X median larger than Y, I take X(median) - 1 , otherwise increase. But that is same algorithm I did for two n-sized array. –  newbieLinuxCpp Jan 29 '13 at 0:07
    
@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
    
Thank you sir,, –  newbieLinuxCpp Jan 29 '13 at 2:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.