Median of two sorted arrays of different size in logarithmic time?

Question

The solution given in Cormen is as follows:

Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary search on A only, then how will we get the median if it lies in B. Also the pseudo code is less than understandable. Can anybody simplify it to me.

Answer 1

Given two sorted arrays $A[1],\ldots,A[\ell]$ and $B[1],\ldots,B[m]$, the goal is to find the median. Let's assume for simplicity that $n := \ell+m$ is odd, and that all elements are distinct. Therefore we are looking for the element which has exactly $\frac{n-1}{2}$ below it in both arrays.

Given an element in one of the arrays, it is easy to find whether it is the median, smaller than the median, or larger than the median. For example, suppose that the element in question is $A[i]$. There are $i-1$ elements below it in $A$. If it were the median, then there would be exactly $j := \frac{n-1}{2} - (i-1)$ elements below it in $B$, which would put it between $B[j]$ and $B[j+1]$. Checking whether this holds, there are three cases:

1. $B[j] < A[i] < B[j+1]$. In this case $A[i]$ is the median.
2. $A[i] < B[j]$. In this case there are fewer than $j$ elements below $A[i]$ in $B$, and so there are fewer than $\frac{n-1}{2}$ elements below $A[i]$. In other words, $A[i]$ is smaller than the median.
3. $A[i] > B[j+1]$. Symmetrically, in this case $A[i]$ is larger than the median.

Suppose that the median belongs to the array $A$. Using the test described above, we can find it using binary search: we start with the middle element of $A$. If it is the median, we're done. If it is larger than the median, we continue with the middle element of the first half of $A$, and if it smaller than the median, we continue with the middle element of the second half of $A$. Continuing in this way, we will eventually find the median in at most (roughly) $\log_2 \ell$ steps.

What if the median doesn't belong to $A$? Our algorithm will get stuck. Since this is an identifiable situation, this suggests an algorithm which finds the median:

1. Try to find the median in $A$ using binary search.
2. If the binary search algorithm gets stuck, find the median in $B$ using binary search.

Note that if the first step fails, the second must succeed. The overall running time is $O(\log \ell + \log m) = O(\log n)$.