algorithm - median of two sorted arrays

Question

My question is with reference to Method 2 of this link. Here two equal length sorted arrays are given and we have to find the median of the two arrays merged.

Algorithm:

1) Calculate the medians m1 and m2 of the input arrays ar1[] 
   and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
     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...|_n/2_|])
    b)  From m2 to last element of ar2  (ar2[|_n/2_|...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_|...n-1])
   b)  From first element of ar2 to m2 (ar2[0...|_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 use below formula to get 
  the median.
    Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2

Example:

   ar1[] = {1, 12, 15, 26, 38}
   ar2[] = {2, 13, 17, 30, 45}

For above two arrays m1 = 15 and m2 = 17

For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.

   [15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:

    m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become

  [15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
                       = (max(15, 13) + min(26, 17))/2 
                       = (15 + 17)/2
                       = 16

I understand how they exclude halves of the arrays and say that the median element would be in particular halves of the arrays i.e. steps 1, 2, 3, 4, 5.

But what I can't fathom, how can they say that the median of the merged arrays would be the median of the merged arrays resulting after pruning the halves of the arrays i.e. the median of merge array of {1, 12, 15, 26, 38} and {2, 13, 17, 30, 45} would be the median of the merge array of {2,13,17} and {15, 26, 38}.

Please explain. Thanks in advance.

Answer 1

Let me help you visualize it. Lets say it is case 3, the same argument follows for the other case. That means we have identified the median is present in 1st half of ar1 or second half of ar2. Now the question is why is the median of these halves same as the median of the original arrays, right.

So visualize putting just these relevant halves together in sorted order and finding its median. Now put the other left over halves back into this picture, where would they go. The first half of ar2, all n/2 elements have to go to the top of this new median and second half of arr1 all n/2 elements will have to go below this median (the exact locations is unimportant for median). So that means it will still be a median as equal number of elements are added above and below it. So the median of the two new halves is same as the median of the original set.

To be still more precise, let's see why first half of ar2 (a leftover half) has to go above the new median. That is the case because when we put all the elements together m2 has to go above the new median(since m2 < m1) which means all the first half of ar2 also have to go above the new median. In other words if m is the new median of the 2 selected halves, m2 < m => all first half of ar2 < m. Similar argument for the lower half of ar1. This means the new median m will remain the median of the entire set.

Looking more closely at your algo., though the approach is correct there might be a slight error in the algo while taking care of odd and even cases so beware while implementing.