1
$\begingroup$

This problem is from Algorithms, problem 2

The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($log n$) time algorithm to find the median of the 2$n$ lists.'

My question is regarding the case where median($X$) is less than the median($Y$).

Here is the proof that the authors(gave) that any element in $X$ less than median($X$) cannot be the median of the two lists.

  1. Suppose an element e is in $A$ and e $\lt$ median($X$). Then there will be less than $\frac12n$ elements less than e(in $X$)
  2. Since e $\lt$ median($X$) $\lt$ median($Y$) there are less than $\frac12n$ elements less than e(in $B$)

Because of 1 and 2, the median cannot be any element in $A$ that is less than median($A$)

I agree with every step in the proof and with that statement. However, here is the diagram of possibilities where the median of the two lists can be

enter image description here

Based off that proof, I understand why all the elements below the median of $A$ and in $A$ cannot be the median of the two lists. But what justification did author use to eliminate median($X$) as a possibility? It wasn't included in the shaded region.

$\endgroup$
4
$\begingroup$

$X_m$ and $Y_m$ are not shaded, because each of them is potentially the median of $X \cup Y$.

Consider two examples (Below I take the $\lfloor (n+1)/2 \rfloor$-th element as the median of an array of size $n$):

(1) $X = \{ 2, 4, 6 \}$ and $Y = \{ 3, 5, 7 \}$.

(2) $X = \{ 2, 4, 6 , 8 \}$ and $Y = \{ 3, 5, 7, 9 \}$.

I think the caption of Figure 1 is wrong: median of two sorted lists lies in the unshaded region.

$\endgroup$
  • $\begingroup$ I agree each of them is potentially the median. But in the diagram, the shaded region is where the median could lie so it should be shaded. That's what I was confused about $\endgroup$ – committedandroider Apr 30 '15 at 16:28
  • $\begingroup$ @committedandroider I think the caption of Figure 1 is wrong: median of two sorted lists lies in the unshaded region. $\endgroup$ – hengxin May 4 '15 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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