arrays - 找到两个排序数组的中位数 - 我得到 stackoverflow 异常

Question

问题给定两个排序的数组，在O(log n) 中找到两者的中位数。合并排序的数组并找到中位数(在 n/2)应该可行。但我猜这是 O(n) 时间，它需要辅助存储。我找到了这个 pseudocode (pdf 中的问题 2)。当我执行该代码时，我得到了 stackoverflow exception。这是我的代码:

public static int quickMedian(int[] arr1, int[] arr2, int startArr1, int endArr1, int startArr2, int endArr2){  
        int m1=(endArr1-startArr1)/2;
        int m2=(endArr2-startArr2)/2;
        if (arr1[m1]==arr2[m2])
            return arr1[m1];
        if (arr1[m1]<arr2[m2])
            return quickMedian(arr1, arr2, m1, endArr1, startArr2, m2);
        else 
            return quickMedian(arr1, arr2, startArr1, m1, m2, endArr2);
    }

public static void main (String[] args){
        int[] arr1={1,3,5,7};
        int[] arr2={2,4,6,8};
        int[] arr3={1,2,4,6,8,10,11};
        System.out.println(quickMedian(arr1, arr2, 0, arr1.length-1, 0, arr2.length-1));
    }

我需要帮助修复 stackoverflow 异常 并使其正常工作。谢谢。

Answer 1

问题是结束条件

if (arr1[m1]==arr2[m2])
        return arr1[m1];

因为它允许算法无限期运行，如果中值不存在于两个数组中。因此 quickMedian() 方法被一遍又一遍地调用，直到堆栈空间用完。

编辑:

我进一步分析了伪代码，我可以满意地说该算法存在根本性缺陷。该算法的要点是取两个数组，将它们分成两半，丢弃不包含中位数的两半，然后对其余数组重复。

这种方法的问题是，当我们丢弃不包含中位数的一半数组时，我们剩下两个包含中位数的数组，但不能保证原始数组的中位数减半那些将是相同的。如果一个数组包含的元素多于另一个，则会从一个数组中丢弃更多元素，并且新数组的中位数可能会发生变化。

a1 = {1,2,3,4,6,7,8,9}    median = 6
a2 = {5}                  median = 5

// median of a1 + a2 is 5

第一步之后:

a3 = {1,2,3,4}            median = 3
a4 = {5}                  median = 5

// median of a3 + a4 is 3

a3 + a4 的中位数现在将为 3，因为三个高于 5 的元素已被删除，但没有低于 5 的元素。确实，原始数组的中位数是 在 两个新数组中，但它与新数组的中位数 不是同一个元素。因此，无论应用多少补丁和修复，这种递归方法都不起作用。因此，我还建议考虑合并两个数组。