Interview Question
Almost there. Since there are 2N elements, the median will be the average of the Nth and (N+1)st entries.
Well...
Depends on your definition of median.
The way I know it is that the median(s) of a set belong to it. So in case of even number of elements, there are two medians, the Nth and N+1st.
Keep two pointers to the arrays, go as in merge-sort's merge step, stop at the Nth entry. It will be in either of the two arrays. Return the value.
- Ananamas October 22, 2009