java - 两个排序数组的中位数 : Termination condition failing

Question

下面的代码是我按照 Median of two sorted arrays (method - 2) 中的逻辑编写的

您甚至可以在 Ideone.com 查看代码

class MedianOfTwoArrays {
    public static void main(String[] args) {
        // Note: These are sorted arrays and are of equal length.
        int[] array1 = {1, 12, 15, 26, 38};
        int[] array2 = {2, 13, 17, 30, 45};

        int median = getMedianOfTwoArrays(array1, array2);
        System.out.println(median);
    }

    static int getMedianOfTwoArrays(int[] array1, int[] array2) {
        int index1 = array1.length/2;
        int index2 = array2.length/2;

        int m1 = array1[index1];
        int m2 = array2[index2];

        if(m1 == m2) {
            return m1;
        } else {
            return findMedian(array1, array2, 0, array1.length - 1, 0, array2.length - 1);
        }
    }


    static int findMedian(int[] array1, 
                            int[] array2, 
                                int low1, 
                                    int high1, 
                                        int low2, 
                                            int high2) {


        if((high1 - low1 + 1) == 2 && (high2 - low2 + 1) == 2) {
                return (Math.max(array1[low1], array2[low2]) + Math.min(array1[high1], array2[high2]))/2;
        }

        int mid1 = (low1 + high1)/2;
        int mid2 = (low2 + high2)/2;

        int m1 = array1[mid1];
        int m2 = array2[mid2];

        int low1_t = 0;
        int high1_t = 0;
        int low2_t = 0;
        int high2_t = 0;

        if(m1 == m2) {
            return m1;
        } else if(m1 > m2) {
            low1_t = low1;
            high1_t = mid1;
            low2_t = mid2;
            high2_t = high2;
            return findMedian(array1, array2, low1_t, high1_t, low2_t, high2_t);
        } else {
            low1_t = mid1;
            high1_t = high1;
            low2_t = low2;
            high2_t = mid2;
            return findMedian(array1, array2, low1_t, high1_t, low2_t, high2_t);
        }
    }
}

它不适用于像这样的输入数组，

int[] array1 = {1, 5, 17, 20}; // median is 10
int[] array2 = {4, 8, 13, 19};

int[] array1 = {1, 3, 5, 7, 9, 11}; // median is 6
int[] array2 = {2, 4, 6, 8, 10, 12};

根据我的分析，问题是终止条件。 geeksforgeeks 提出的一些逻辑似乎与终止条件有关。

(Math.max(array1[low1], array2[low2]) + Math.min(array1[high1], array2[high2]))/2;

但我无法解决它并使其适用于上述输入。 有人可以调查这个问题并让我知道我在哪里犯了错误吗？

Answer 1

你的主要错误是，当你做普通的 int mid1 = (low1 + high1)/2; 你的 mid1 总是向左移动，然后你分配mid1 不考虑这种移位，因此每个嵌套比较都会比较从预期位置向左移动的数组元素，并且由于长度为 2n 的数组的中值总是a[n-1]+a[n]/2，您在第一次执行比较后比较了错误的数组元素。您似乎错误地实现了方法 2 的这段代码:

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

事实上，findMedian() 入口处的简单assert (high2-low2==high1-low1) 会提醒您不正确的逻辑，因为对于数组大小为 4 的第二个入口产生不相等的数组大小。退出条件非常好，因为它是直接从方法 2 的代码中复制的。因此，需要将low1_t等赋值的block改成如下:

    assert (high2-low2==high1-low1); // sanity check
    int n=high1-low1+1; // "n" from logic

    int m1 = median(array1,low1,high1);
    int m2 = median(array2,low2,high2);

    int low1_t = low1;
    int high1_t = high1;
    int low2_t = low2;
    int high2_t = high2;

    if(m1 == m2) {
        return m1;
    } else if(m1 > m2) {
        if (n % 2 == 0) {
            high1_t = high1-n/2+1;
            low2_t = low2+n/2-1;
        } else {
            high1_t = high1-n/2;
            low2_t = low2+n/2;
        }
    } else {
        if (n % 2 == 0) {
            low1_t = low1+n/2-1;
            high2_t = high2-n/2+1;
        } else {
            low1_t = low1+n/2;
            high2_t = high2-n/2;
        }
    }
    return findMedian(array1, array2, low1_t, high1_t, low2_t, high2_t);

然后像这样添加函数median:

static int median(int[] arr, int low,int hig) 
{
    if ((low+hig)%2 == 0) return arr[(low+hig)/2];
    int mid=(low+hig)/2;
    return (arr[mid]+ arr[mid-1])/2;
}

完整示例(根据需要更改数组):http://ideone.com/zY30Vg