两个排序数组的中位数 [英] median of two sorted arrays

问题描述

我的问题是参考此链接的方法2.这里给出了两个等长排序的数组，我们必须找到合并的两个数组的中位数.

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

我了解，他们如何排除数组的一半，并说中位数元素将特别是数组的一半，即步骤1、2、3、4、5 .

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.

但是我不能理解，他们怎么说，合并数组的中位数将是对数组的一半进行修剪后得到的合并数组的中位数，即 {1，12，15，26，38}和{2，13，17，30，45}的合并数组的中位数将是{2,13,17}和{15，26， 38}.

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}.

请解释.预先感谢.

推荐答案

让我帮助您对其进行可视化.可以说是第3种情况，其他情况也采用相同的论点.这意味着我们已经确定中值出现在ar1的上半部分或ar2的下半部分中.现在的问题是，为什么这两个半数的中位数与原始数组的中位数相同，对.

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.

因此可视化地将这些相关的两部分按排序顺序放在一起并找到其中间值.现在，将剩下的两半放回这张照片中，它们会去哪里. ar2的前半部分，所有n/2个元素都必须到达此新中位数的顶部，而arr1的后半部分，所有n/2个元素都必须低于该中位数(确切位置对于中位数而言并不重要).因此，这意味着它的上方和下方均会添加相同数量的元素，因此仍为中位数.因此，两个新的半部分的中位数与原始集合的中位数相同.

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.

更准确地说，让我们看看为什么ar2的前半部分(剩余的一半)必须高于新的中位数.之所以如此，是因为当我们将所有元素放在一起时，m2必须高于新的中位数(因为m2 ar2的所有前半部分<米ar1的下半部分也有类似的论点.这意味着新的中位数m将仍然是整个集合的中位数.

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.

这篇关于两个排序数组的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！