c++ - 为什么找到 2 个不同大小的排序数组的中位数需要 O(log(min(n,m)))

Question

请考虑这个问题:

我们有 2 个不同大小的排序数组，A[n] 和 B[m]； 我已经实现了一个最多需要 O(log(min(n,m))) 的经典算法。

方法如下: 开始将两个数组分成两组一半(不是两部分，但两个分区应该具有相同数量的元素)。前半部分包含第一个和第二个数组中的一些第一个元素，下半部分包含第一个和第二个数组中的其余(或最后一个)元素。因为数组可以有不同的大小，所以并不意味着从每个数组中取一半。达到一个条件，使得前半部分的每个元素都小于或等于后半部分的每个元素。

请看上面的代码:

double median(std::vector<int> V1, std::vector<int> V2) 
{
    if (V1.size() > V2.size())
    {
        V1.swap(V2);
    };
    int s1 = V1.size();
    int s2 = V2.size();
    int low = 0;
    int high = s1;
    while (low <= high) 
    {
        int px = (low + high) / 2;
        int py = (s1 + s2 + 1) / 2 - px;

        int maxLeftX = (px == 0) ? MIN : V1[px - 1];
        int minRightX = (px == s1) ? MAX : V1[px];

        int maxLeftY = (py == 0) ? MIN : V2[py - 1];
        int minRightY = (py == s2) ? MAX : V2[py];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) 
        {
            if ((s1 + s2) % 2 == 0) 
            {
                return (double(std::max(maxLeftX, maxLeftY)) + double(std::min(minRightX, minRightY)))/2;
            }
            else 
            {
                return std::max(maxLeftX, maxLeftY);
            }
        }
        else if(maxLeftX > minRightY)
        {
            high = px - 1;
        }   
        else
        {
            low = px + 1;
        }
    }
    throw;
}

虽然该方法非常简单并且有效，但我仍然无法说服自己它的正确性。此外，我无法理解为什么它需要 O(log(min(n,m)) 个步骤。

如果有人能简要解释正确性以及为什么它需要 O(log(min(n,m))) 步，那将是很棒的。即使您可以提供带有有意义解释的链接。

Answer 1

时间复杂度非常简单，您可以通过二进制搜索元素较少的数组来找到这样的分区，从而找到中位数。您精确地执行了 O(log(#elements)) 个步骤，并且由于您的 #elements 正好是 min(n, m)，所以复杂度是 O(log(min(n+m))。

恰好有 (n + m)/2 个元素小于中位数和相同数量的元素大于中位数。让我们将它们视为两半(让中位数属于您的选择之一)。

您当然可以将较小的数组分成两个子数组，其中一个完全位于前半部分，第二个完全位于另一半。但是，您不知道其中有多少元素。

让我们选择一些 x - 你对前半部分较小数组中元素数量的猜测。它必须在 0 到 n 的范围内。然后你知道，因为恰好有 (n + m)/2 个元素小于中位数，你必须从更大的数组中选择 (n+m)/2 - x 个元素。然后您必须检查该分区是否真的有效。

要检查分区是否良好，您必须检查小半部分中的所有元素是否都小于大半部分中的所有元素。您必须检查 maxLeftX <= minRightY 以及 maxLeftY <= minRightX(然后左半部分的每个元素都小于右半部分的每个元素)

如果是这样，您就找到了正确的分区。您现在可以轻松找到您的中位数(它可以是 max(maxLeftX, maxLeftY))、min(minRightX, minRightY) 或它们的总和除以 2)。

如果不是，您要么从较小的数组中获取了太多元素(当 maxLeftX > minRightY 时的情况)，那么下次您必须猜测 x 的较小值，或者它们太少，然后您必须猜测更大的值对于 x。

为了获得最佳复杂度，请始终猜测 x 可能取值范围的中间值。