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

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

我们知道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 步所做的。