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