1
$\begingroup$

The solution given in Cormen is as follows:

Median

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.

$\endgroup$
  • $\begingroup$ The code handles your first doubt in lines 1-2. $\endgroup$ – Yuval Filmus Jul 28 '18 at 11:55
  • $\begingroup$ But how that is the question @YuvalFilmus . Can you explain their ideology in a bit detail. A mere paragraph for such a hard problem is injustice. $\endgroup$ – Navjot Waraich Jul 28 '18 at 12:15
  • $\begingroup$ You try to find the median in A. If you fail, you try again in B. $\endgroup$ – Yuval Filmus Jul 28 '18 at 12:53
  • $\begingroup$ I think the solution has a small error in that it should say $j=\left \lfloor{n/2}\right \rfloor - (i-1)$ instead of a ceiling function. Then in the pseudocode, it should say that instead of $\left\lceil{n/2}\right\rceil - i$. Just so anyone else gets confused like I did... $\endgroup$ – Glassjawed Apr 8 at 23:39
  • $\begingroup$ Seems like @YuvalFilmus said that already in his answer, oops! $\endgroup$ – Glassjawed Apr 8 at 23:40
3
$\begingroup$

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

$\endgroup$

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.