edited by
3,218 views
25 votes
25 votes

It takes $O(n)$ time to find the median in a list of $n$ elements, which are not necessarily in sorted order while it takes only $O(1)$ time to find the median in a list of $n$ sorted elements. How much time does it take to find the median of $2n$ elements which are given as two lists of $n$ sorted elements each?

  1. $O (1)$
  2. $O \left(\log n\right)$ but not $O (1)$
  3. $O (\sqrt{n})$ but not $O \left(\log n\right)$
  4. $O (n)$ but not $O (\sqrt{n})$
  5. $O \left(n \log n\right)$ but not $O (n)$
edited by

2 Answers

Best answer
36 votes
36 votes
  1. Calculate the medians $m1$ and $m2$ of the input arrays $ar1[\ ]$ and $ar2[ \ ]$ respectively.
  2. If $m1$ and $m2$ both are equal,
    return $m1$ (or $m2$)
  3. If $m1$ is greater than $m2$, then median is present in one of the below two subarrays.
        (a)  From first element of $ar1$ to $m1$ $(ar1[0$ to $n/2])$
        (b)  From $m2$ to last element of $ar2$  $(ar2[n/2$ to $n-1])$
  4. If $m2$ is greater than $m1$, then median is present in one of the below two subarrays.
       (a)  From $m1$ to last element of $ar1$  $(ar1[n/2$ to $n-1])$
       (b)  From first element of $ar2$ to $m2$ $(ar2[0$ to $n/2])$
  5. Repeat the above process until size of both the subarrays becomes $2$.
  6. If size of the two arrays is $2$ then,
    Median $= (\max(ar1[0], ar2[0]) + \min(ar1[1], ar2[1]))/2$
    Time complexity $O(\log n)$

http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

Correct Answer: $B$

edited by
Answer:

Related questions