查找相同大小的2个数组的中位数-O（log n）算法无法产生正确的结果

Question

我正在尝试解决计算具有相同元素但具有不同元素的合并的两个排序数组的中位数的问题。

算法来源：https://www.geeksforgeeks.org/median-of-two-sorted-arrays/该算法已在Internet上的多个来源中用作O（log n）解决方案。但是，我认为它不适用于我制作的示例。

我的反例：

我们有2个没有重复的排序数组：

[2,3,12,14]＆[1,5,8,9]

合并的排序数组是：a = [1,2,3,5,8,9,12,14]中位数：13/2 = 6.5

以下算法：

[2,3,12,14]的中位数是(3+12)/2= 7.5 = m1

[1,5,8,9]的中位数是(5+8)/2 = 6.5 = m2

我们看到m1>m2。因此，遵循该算法，我们考虑第一个数组的前半部分和第二个数组的后半部分。我们有a1 = [2,3]和a2 = [8,9]。

现在我们已经达到一个基本情况，我们得到的结果(max(a1[0],a2[0]) + min(a1[1],a2[1]))/2 = 8+3=11/2=5.5显然不是6.5。

这是我看到的唯一具有O（log n）解决方案的算法，但似乎有缺陷。我在这里缺少什么吗？

Answer 1

不要手工跟踪，运行代码。

这两种算法的Python版本都会为您尝试的反例提供正确的答案。

我不能保证所有实现都能正常工作。但是请记住，您犯错的可能性总是比被许多人认为错误的事情高得多。 （并非总是错误，这就是为什么我在您的示例中运行实际代码。）当您尝试手动跟踪代码时，错误的可能性会大大增加。

Answer 2

为了始终提供第一种方法的相同结果，第二种方法在最后一次迭代中必须以相同的数字结尾。

例如，提供的示例应为6.5

[2，3，12，14]，[1，5，8，9]→[1,2,3，5，8，9，12，14]→（5 + 8）/ 2→6.5

为了确保在用偶数个元素划分范围时，必须将以下元素添加到中间之外：

[2，3，12，14]，[1，5，8，9]→[2，3，12 ]，[5，8，9]→[3、12]，[5、8]→6.5

事实上，您链接的页面中代码的相关部分是这个

int getMedian(int ar1[],  
              int ar2[], int n)
{
    // ...
    if (m1 < m2) 
    { 
        if (n % 2 == 0) 
            return getMedian(ar1 + n / 2 - 1,    // <- Note the difference
                             ar2, n - n / 2 + 1); 
        return getMedian(ar1 + n / 2,            // <-
                         ar2, n - n / 2); 
    } 

    if (n % 2 == 0) 
        return getMedian(ar2 + n / 2 - 1,        // The same here
                         ar1, n - n / 2 + 1); 
    return getMedian(ar2 + n / 2,  
                     ar1, n - n / 2);