两个等长排序数组的中位数

Question

我一直在试图理解为什么下面的算法不起作用。

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

我的难点在于算法的核心步骤3和4。这是我的想法：

如果 m1 > m2 那么 m1 大于合并数组中元素的一半，那么我们为什么要探索 ar1[0...|n/2|]?

Answer 1

看看下面的例子。它展示了您所询问的情况。

ar1[] = {6, 7, 8, 9, 10}
ar2[] = {1, 2, 3, 4, 5}

If m1 > m2 then m1 is greater than half of the elements in the merged array, so why would we want to explore ar1[0...|n/2|]?

理解此算法的关键是查看您在每一步中消除的内容，而不仅仅是保留的内容。的确，由于 m1 > m2，我们知道 m1 大于合并数组中元素的一半。它并没有告诉我们与合并中位数 m1 相关的位置。关于 ar1 和合并中位数之间的关系，我们真正了解的是我们可以消除所有大于 m1 的东西（并且小于 m2 从 ar2 中）。合并列表的中位数在剩余的某处。

ar1[] = {6, 7, 8}
ar2[] = {3, 4, 5}

Answer 2

我们知道m1大于等于ar1的前半部分。 m2 和 ar2 也一样。同时我们也知道m1小于等于ar1的后半部分。

让我们考虑一下 m1 > m2 的情况

ar1:     [.....m1.....]
ar2:     [.....m2.....]
ar1+ar2: [.....m2..m1........]

我们称合并数组的中位数为m*。由于 ar1 和 ar2 的前半部分出现在 m1 之前。我们有 m1 => m*，这意味着在 ar1 中不需要考虑大于 m1 的值。所以我们只需要看前半部分或者ar1.

同样地，由于ar1和ar2的后半部分在m1之后，我们有m2 <= m*，这意味着不需要考虑小于m2的值，我们只需要看后半部分ar2.

这正是第 3 步和第 4 步所做的。

两个等长排序数组的中位数

Median of two sorted arrays of equal length

algorithm

array-algorithms