使用“比较中位数”程序和C++的2个排序数组的中位数

Question

我看了一段Youtube的视频，视频中一些学生演示了不同的算法来求出两个排序数组的中位数:算法详见：https://www.youtube.com/watch?v=_H50Ir-Tves。我正在尝试实现他的“比较中值”算法，结果遇到了栅栏问题之类的问题。我决定将“中位数”定义为N元素数组中的元素N/2。我的实现总体上是杂乱无章的，而且无法正常工作。

下面是我用来比较我的另一个函数的函数：

template <typename T>
T M2SA_Dumb(std::vector<T> A, std::vector<T> B)
{

    if (A.size() == 0 || B.size() == 0)
        throw std::invalid_argument("Can't find median of 2 sorted arrays if both are empty!");
    std::vector<T> AB;
    AB.reserve(A.size() + B.size());
    AB.insert(AB.end(), A.begin(), A.end());
    AB.insert(AB.end(), B.begin(), B.end());
    sort(AB.begin(), AB.end());
    return (AB[AB.size() / 2]);
}

下面是我正在尝试调试的非工作函数：

template <typename T>
T M2SA_Smart(const std::vector<T> & A, const std::vector<T> & B)
{
    size_t m(A.size()), n(B.size());
    T retval;
    size_t sizeval = (m > 0 ? 1 : 0) + 2 * (n > 0 ? 1 : 0);
    switch (sizeval)
    {
    case 0: // A, B empty
        throw std::invalid_argument("Can't find median of 2 sorted arrays if both are empty!");
        break;
    case 1: // A non-empty, B empty
        retval = A[m / 2];
        break;
    case 2: // A empty, B non-empty
        retval = B[n / 2];
        break;
    default: // A, B non-empty
        size_t medidx = (m + n) / 2;
        if (A[m - 1] <= B[0])
        {
            if (medidx >= m)
            {
                retval = B[medidx - m];
            }
            else
            {
                retval = A[medidx];
            }
        }
        else if (B[n - 1] <= A[0])
        {
            if (medidx >= n)
            {
                retval = A[medidx - n];
            }
            else
            {
                retval = B[medidx];
            }
        }
        else
        {
            size_t a1(0), a2(m - 1), b1(0), b2(n - 1);
            T M1(A[(a2 - a1) / 2]), M2(B[(b2 - b1) / 2]);
            while (a1 != a2 && b1 != b2)
            {
                if (M1 == M2)
                {
                    retval = M1;
                    break;
                }
                else if (M1 < M2)
                {
                    a1 = (a2 - a1) / 2;
                    b2 = (b2 - b1) / 2;
                }
                else
                {
                    a2 = (a2 - a1) / 2;
                    b1 = (b2 - b1) / 2;
                }
                M1 = A[(a2 - a1) / 2];
                M2 = B[(b2 - b1) / 2];
            }
            retval = std::max(M1, M2);
        }
        break;
    }
    return retval;
}

我认为问题出在递归部分。

    {
        size_t a1(0), a2(m - 1), b1(0), b2(n - 1);
        T M1(A[(a2 - a1) / 2]), M2(B[(b2 - b1) / 2]);
        while (a1 != a2 && b1 != b2)
        {
            if (M1 == M2)
            {
                retval = M1;
                break;
            }
            else if (M1 < M2)
            {
                a1 = (a2 - a1) / 2;
                b2 = (b2 - b1) / 2;
            }
            else
            {
                a2 = (a2 - a1) / 2;
                b1 = (b2 - b1) / 2;
            }
            M1 = A[(a2 - a1) / 2];
            M2 = B[(b2 - b1) / 2];
        }
        retval = std::max(M1, M2);
    }

一定有什么奇怪的事情在发生。你知道这是什么吗？

有关更多信息，请参见

我测试了

std::vector<int> v1 = { 1, 1, 69, 111, 124 };
std::vector<int> v2 = { 40, 50, 60, 70, 80, 90, 100, 110, 120, 130 };

并得到了

M2SA_Dumb(v1, v2) = 80 (正确答案)

和

M2SA_Dumb(v1, v2) = 40 (错误答案)

Answer 1

视频中显示的算法旨在处理两个大小相同的数组或向量。此外，偶数个元素数组的中位数通常定义为中间两个元素的平均值(因此它可以是以.5结尾的浮点值)。

链接到针对不同大小的数组的更通用的算法：

median of different size sorted arrays

我不确定这是否实用。在大多数当前的PC上，使用合并排序或快速排序，可以在不到1秒的时间内对400万个64位整数的数组或向量进行排序。两个有序数组或向量的std：：合并，或者两个有序列表的std：：list：：合并只需要一小部分时间。