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 可能采用的一系列可能值的中间位置。