“两个已排序数组的中位数”算法解析

Question

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

double findMedianSortedArrays(int A[], int m, int B[], int n) {
    return findMedianHelper2(A, m, B, n, max(0, (m-n)/2), min(m-1, (m+n)/2));
}

double findMedianHelper2(const int A[], const int m, const int B[], const int n, const int l, const int r) {
    if (l > r) return findMedianHelper2(B, n, A, m, max(0, (n-m)/2), min(n-1, (m+n)/2));

    int i = (l+r)/2;
    int j = (m+n)/2-i;

    assert(i >= 0 && i <= m && j >= 0 && j <= n);
    int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
    int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
    int Ai = ((i == m) ? INT_MAX : A[i]);
    int Bj = ((j == n) ? INT_MAX : B[j]);

    if (Ai < Bj_1) return findMedianHelper2(A, m, B, n, i+1, r);
    if (Ai > Bj) return findMedianHelper2(A, m, B, n, l, i-1);

    if (((m+n) % 2) == 1) return A[i];
    return (max(Ai_1, Bj_1) + Ai) / 2.0;
}

问题：选择l = max(0, (m-n)/2)和r = min(m-1, (m+n)/2)的意义是什么？

谢谢。

- q0987

---

你可能会从这个问题中得到一些更一般的澄清：https://dev59.com/OWjWa4cB1Zd3GeqPt8ZI。 - Daniel Fischer

请参见https://dev59.com/Qm025IYBdhLWcg3wKCf-。 - Nemo

Answer 1

对我来说，那段代码没有意义。然而，我认为关键在于确保 m>n 并且正确传递值 (m-n)/2 和 (m+n)/2 到辅助函数中。此外，从辅助函数开头的 if 语句可以看出，意图是在 m<n 时修复问题。

假设 m>0 且 n>0（它们必须如此才能使数组有意义）。
如果 m>n，则在辅助函数内部，(l>r) 将为 false，算法应该能够正常工作。
如果 m<n，则在辅助函数内部，(l>r) 将为 false（除非 m=1），而“修复”似乎根本没有修复任何东西。

因此，我认为代码在开头有些问题。
然而，主要部分对我来说似乎是有意义的，并确实帮助我用 JAVA 实现了相同的功能。

- tgeng

---

抱歉，这是我第一次在StackOverflow上发帖，我没有意识到我正在输入HTML代码。 - tgeng

Answer 2

首先，让我们证明m=n的情况下的算法。

• 将中间元素命名为“k”

  m1:=A[n/2]

  m2:=B[n/1]`

  如果m1 < m2，则m1 < k < m2，否则m2 < k < m1。

  证明：m1 < k，所以假设m2 < k，但这是不正确的：“k”元素的索引显然比n高。因此，m2 > k。

如果m1 > k同样的道理，我们有m2 < k。

• A和B合并的中间元素将是A/2和B/2合并的中间元素。 因此，我们需要继续在两个数组中查找元素：A/2和B/2，直到数组变得相等。

- user2254651

Answer 3

选择这样的左右索引的原因是为了跳过不能成为两个排序数组中位数的元素。

不失一般性，我们假设m>n。那么有两种边缘情况：

即使B中的所有元素都小于A[0]，中位数仍然不可能是A[0，...，（m-n）/2-1]中的元素，因为n +（m-n）/2-1 <（m + n）/2。

同样地，即使B中的所有元素都大于A[m-1]，中位数仍然不可能是A[(m + n) / 2 + 1，...，m-1]中的元素，因为A[(m + n) / 2]必须是中位数。

基于这个观察结果，我们只需要在较长数组的子数组上执行二分查找以找到中位数。

对于 m < n 的情况，l = max(0, (m-n)/2) = 0 且 r = min(m-1, (m+n)/2) = m - 1，这意味着中位数可能是较短数组中的任何元素。

- Ziyun

Answer 4

http://leetcode.com/2011/03/median-of-two-sorted-arrays.html 这是该算法的详细分析

- zangw

Answer 5

问题：选择l = max(0，（m-n）/2)和r = min(m-1，（m+n）/2)的含义是什么？

MAX和MIN用于夹紧值，使其不能低于或高于约束。

IF m - n < 0 THEN
    l = 0
ELSE l = (m - n) / 2

IF (m + n) / 2 > m - 1 THEN
    r = m -1
ELSE r = (m + n) / 2

- Louis Ricci

---

这是一个很好的代码解释，但它并没有解决我的问题。我不理解为什么我们可以在这个算法中应用这个约束条件。这个设置背后的理论是什么？-谢谢 - q0987

@q0987 - 也许你可以在每次迭代中将值输出到控制台或调试器，这样你就可以了解 l 和 r 是如何被使用的。当 n 和 m 不相等时，l 和 r 充当纠正措施。这使得 i 和 j 始终在数组的边界内（因此有断言）。 - Louis Ricci

其实，在我发这个问题之前，我已经走过那些步骤了。通过对代码进行调试，我可以看到它是如何工作的。但是我不知道为什么我们可以为 l 和 r 进行这样的选择。 - q0987

@q0987 - 你有两个已排序的列表，如果将它们合并成一个长列表，找到中位数会很容易，但这个合并步骤必须循环遍历它们两个（破坏了Log N时间）。因此，你可以通过比较（Ai，Bj，Ai_1，Bj_1）来移动列表，以尝试推导出它们如果是一个大列表（而不是两个小列表）的中心。 - Louis Ricci