找到相同大小的 2 个数组的中位数 - O(log n) 算法不会产生正确的结果

Question

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

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

我的反例：

我们有 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);

找到相同大小的 2 个数组的中位数 - O(log n) 算法不会产生正确的结果

Finding a median of 2 arrays of the same size - the O(log n) algorithm doesn't yield a correct result

arrays

algorithm

median