java - 理解两个排序数组的中位数算法

Question

有两个有序数组A和B，大小分别为m和n。找到两个排序数组的中位数。整体运行时间复杂度应该是 O(log (m+n))。

我不明白计算 aMid 和 bMid 的公式。这些公式背后的逻辑是什么？

int aMid = aLen * k/(aLen + bLen);//a 的中间计数

int bMid = k - aMid - 1;//b 的中间计数

这是程序的链接。 http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/][1]

public static double findMedianSortedArrays(int A[], int B[]) {
    int m = A.length;
    int n = B.length;

    if ((m + n) % 2 != 0) // odd
        return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
    else { // even
        return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1) 
            + findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
    }
}

public static int findKth(int A[], int B[], int k, 
    int aStart, int aEnd, int bStart, int bEnd) {

    int aLen = aEnd - aStart + 1;
    int bLen = bEnd - bStart + 1;

    // Handle special cases
    if (aLen == 0)
        return B[bStart + k];
    if (bLen == 0)
        return A[aStart + k];
    if (k == 0)
        return A[aStart] < B[bStart] ? A[aStart] : B[bStart];

    int aMid = aLen * k / (aLen + bLen); // a's middle count    
                                      // I AM STUCK HERE

    int bMid = k - aMid - 1; // b's middle count

    // make aMid and bMid to be array index
    aMid = aMid + aStart;
    bMid = bMid + bStart;

    if (A[aMid] > B[bMid]) {
        k = k - (bMid - bStart + 1);
        aEnd = aMid;
        bStart = bMid + 1;
    } else {
        k = k - (aMid - aStart + 1);
        bEnd = bMid;
        aStart = aMid + 1;
    }

    return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}

我从代码的评论中得到了一些想法，这些公式是如何计算的，但仍然不明白向某人解释“为什么这些公式”或者这些公式背后的逻辑是什么？

对于 int aMid = aLen * k/(aLen + bLen);//a 的中间数作为 aMid = aLen/2 --(i)

和k = (aLen + bLen)/2, -->2 = (aLen + bLen)/k

将 2 的值放入 equ (i)

所以 aMid = aLen/(aLen + bLen)/k== aLen *k/(aLen+bLen)

对于 int bMid = k - aMid - 1;//b 的中间计数

必须满足 aMid + bMid + 1 = k 才能得出 A[aMid] > B[bMid] 时的结论

至于为什么 aMid + bMid + 1 = k 很重要:如果 A[aMid] 大于 B[bMid]，你知道 A 中 A[aMid] 之后的任何元素都不可能是第 k 个元素，因为B 中比它低的元素太多(并且会超过 k 个元素)。您还知道 B[bMid] 和 B 中 B[bMid] 之前的任何元素都不能成为第 k 个元素，因为 A 中低于它的元素太少了(在 B[bMid] 之前没有足够的元素来是第 k 个元素)。

Answer 1

正如您已经提到的:aMid + bMid + 1 = k 必须满足才能得出以下结论:
当 A[aMid] > B[bMid] 时，我们可以丢弃 bMid 之前的所有内容以及(包括)aMid 之后的所有内容，
因为我们知道有 bMid + aMid + 1 (来自包括 aMid) = k 小于 A[aMid] 的元素。因此我们的中位数位于剩余的数组中。

考虑到这一点，我们首先如何设置两个中间值 aMid 和 bMid 并不重要。唯一需要注意的是不要让其中之一导致 IndexOutOfBoundsException。

int aMid = 0;
int bMid = k - aMid - 1;
if(bMid >= bLen) {
    bMid = bLen - 1;
    aMid = k - bMid - 1;
}

也可以解决这个问题。但这将花费超过 O(log(n+m)) 的时间，因为在最坏的情况下我们总是只跳过一个元素 (A[0])。
我们想要的是始终丢弃一定百分比的 aLen + bLen。
在我们的例子中是:

A > B: k = k - (bMid +1) = k - (k - aMid) = aMid = k * (aLen / (aLen + bLen))
B > A: k = k - (aMid + 1) = k - (k * aLen / (aLen + bLen)) -1 = k * (bLen / (aLen + bLen)) - 1

忽略 -1 并假设 A > B 的概率与 B > A 相同，我们得到:
E(k ) = 0.5 * k * (aLen/(aLen + bLen)) + 0.5 * k * (bLen/(aLen + bLen))
= 0.5 * k (aLen + bLen)/(aLen + bLen) = 0.5 * k
这意味着我们得到大约 O(log(n + m)) 次递归调用，直到 k 为 0，然后函数停止。