中位数的中位数算法误解？

Question

我已经理解的内容

我理解中位数算法（我将其表示为MoM）是一个高常数因子O(N)算法。它查找k组（通常是5个）的中位数，并将它们用作下一次迭代的集，以查找中位数。在找到这个后，枢轴将在原始集的3/10n和7/10n之间，其中n是找到一个中位数基本情况所需的迭代次数。

当我运行MoM代码时，我一直收到分段错误的提示，但我不知道为什么。我已经调试过了，并认为问题在于我调用了medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);。然而，我认为这在逻辑上是正确的，因为我们应该通过调用自身来递归地找到中位数。也许我的基本情况不正确？在Youtube上由斯坦福教授YogiBearian制作的教程中（链接：https://www.youtube.com/watch?v=YU1HfMiJzwg），他没有说明任何额外的基本情况来处理MoM中递归的O(N/5)操作。

完整代码

注意：根据建议，我添加了一个基本情况，并使用了向量的.at（）函数。

static const int GROUP_SIZE = 5;
/* Helper function for m of m. This function divides the array into chunks of 5 
 * and finds the median of each group and puts it into a vector to return.
 * The last group will be sorted and the median will be found despite its uneven size.
 */
vector<int> findMedians(vector<int>& vec, int start, int end){
    vector<int> medians;
    for(int i = start; i <= end; i+= GROUP_SIZE){
        std::sort(vec.begin()+i, min(vec.begin()+i+GROUP_SIZE, vec.end()));
        medians.push_back(vec.at(min(i + (GROUP_SIZE/2), (i + end)/2)));
    }
    return medians;
}

/* Job is to partition the array into chunks of 5(subject to change via const)
 * And then find the median of them. Do this recursively using select as well.
 */
int medianOfMedian(vector<int>& vec, int start, int end, int k){
    /* Acquire the medians of the 5-groups */
    vector<int> medians = findMedians(vec, start, end);

    /* Find the median of this */
    int pivotVal;
    if(medians.size() == 1)
        pivotVal = medians.at(0);
    else
        pivotVal = medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);

    /* Stealing a page from select() ... */
    int pivot = partitionHelper(vec, pivotVal, start, end);

    cout << "After pivoting with the value " << pivot << " we get : " << endl;
    for(int i = start; i < end; i++){
        cout << vec.at(i) << ", ";
    }
    cout << "\n\n" << endl;
    usleep(10000);
    int length = pivot - start + 1;
    if(k < length){
        return medianOfMedian(vec, k, start, pivot-1);
    }
    else if(k == length){
        return vec[k];
    }
    else{
        return medianOfMedian(vec, k-length, pivot+1, end);
    }

}

一些帮助单元测试的额外函数

这里是我为这两个函数编写的一些单元测试。希望它们能有所帮助。

vector<int> initialize(int size, int mod){
    int arr[size];
    for(int i = 0; i < size; i++){
    arr[i] = rand() % mod;
    }
    vector<int> vec(arr, arr+size);
    return vec;
}

/* Unit test for findMedians */
void testFindMedians(){
    const int SIZE = 36;
    const int MOD = 20;
    vector<int> vec = initialize(SIZE, MOD);
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;

    vector<int> medians = findMedians(vec, 0, SIZE-1);

    cout << "The 5-sorted version: " << endl;
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;

    cout << "The medians extracted: " << endl;
    for(int i = 0; i < medians.size(); i++){
        cout << medians[i] << ", ";
    }
    cout << "\n\n" << endl;
}

/* Unit test for medianOfMedian */
void testMedianOfMedian(){
    const int SIZE = 30;
    const int MOD = 70;
    vector<int> vec = initialize(SIZE, MOD);
    cout << "Given array : " << endl;
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;
    int median = medianOfMedian(vec, 0, vec.size()-1, vec.size()/2); 
    cout << "\n\nThe median is : " << median << endl;

    cout << "As opposed to sorting and then showing the median... : " << endl;
    std::sort(vec.begin(), vec.end());
    cout << "sorted array : " << endl;
    for(int i = 0; i < SIZE; i++){
        if(i == SIZE/2)
            cout << "**";
        cout << vec[i] << ", ";
    }
    cout << "Median : " << vec[SIZE/2] << endl;
}

关于我得到的输出的额外说明

Given array :
7, 49, 23, 48, 20, 62, 44, 8, 43, 29, 20, 65, 42, 62, 7, 33, 37, 39, 60, 52, 53, 19, 29, 7, 50, 3, 69, 58, 56, 65,

After pivoting with the value 5 we get :
23, 29, 39, 42, 43,

After pivoting with the value 0 we get :
39,

Segmentation Fault: 11

似乎一切都很好，直到出现了“分段错误”。我相信我的分区函数也可以正常工作（这是解决LeetCode问题的实现之一）。

免责声明：这不是一个作业问题，而是在我使用quickSelect解决LeetCode问题集后对算法的好奇。

如果我的问题需要更详细的MVCE阐述，请告诉我，谢谢！

编辑：我发现我的代码中递归分区方案是错误的。正如Pradhan指出的那样，我不知怎么搞的，有空向量导致起始和结束都为0和-1，导致我从无限循环的调用中出现分段错误。仍在努力解决这一部分。

- OneRaynyDay

---

请使用vector::at()替换您访问向量元素的[ ]用法。为什么？为了确保在访问向量项时不会越界。如果您越界，at()将抛出异常，提供更多信息。如果您只使用[ ]，则如果您越界，则代码的行为是未定义的。关于向量和段错误的问题已经有过几篇SO文章，几乎总是可以通过使用at()来识别边界访问问题来发现解决方案。 - PaulMcKenzie

@PaulMcKenzie 啊 - 谢谢！我之前不知道这个功能。我现在会使用它并继续调试，然后汇报结果 :) - OneRaynyDay

我认为 min(vec.begin()+i+GROUP_SIZE, vec.end()) 应该是 min(vec.begin()+i+GROUP_SIZE, vec.begin()+end)。 - Sergey Kalinichenko

@PaulMcKenzie 编辑过，而 @dasblinkenlight 我改了但没有影响输出。我相信迭代器算术在 vec.begin()+end 和 vec.end() 上的行为是相同的。 - OneRaynyDay

Answer 1

MoM总是调用自身（来计算pivot），从而呈现出无限递归。这违反了递归算法的“首要指令”：在某个时刻，问题会变得“小”到不需要递归调用。

- Scott Hunter

---

嗨 - 很好的发现！不过，它没有修复我的分段错误。(另外，一个无限循环在显示中会非常明显，但分段错误不会由无限循环创建，是吧?) 它现在已经被编辑了，并增加了一个“逻辑”基本情况。我希望我走对了路。 - OneRaynyDay

当超过允许的堆栈大小限制时，无限递归会导致段错误。 - Pradhan

@OneRaynyDay，你能否检查一下findMedians函数是否会出现end < start的情况？ - Pradhan

@OneRaynyDay 这是我在你的代码中看到的唯一无限递归路径 :) 由于你已经消除了越界访问，因此这似乎是最可能的原因。 - Pradhan

让我们在聊天中继续这个讨论。 - OneRaynyDay

Answer 2

正确的实现

在Scott的提示下，我成功地实现了这个中位数算法的正确版本。我进行了修复并意识到我的主要思路是正确的，但有一些错误：

• 我的基本情况应该是子向量大小<=5。

• 关于最后一个数字（变量end）是否应该被视为包含或作为上限小于的一部分，有一些微妙之处。在下面的实现中，我将其定义为上限小于。

以下是代码。我也接受了Scott的答案-谢谢Scott！

/* In case someone wants to pass in the pivValue, I broke partition into 2 pieces.
 */
int pivot(vector<int>& vec, int pivot, int start, int end){

    /* Now we need to go into the array with a starting left and right value. */
    int left = start, right = end-1;
    while(left < right){
        /* Increase the left and the right values until inappropriate value comes */
        while(vec.at(left) < pivot && left <= right) left++;
        while(vec.at(right) > pivot && right >= left) right--;

        /* In case of duplicate values, we must take care of this special case. */
        if(left >= right) break;
        else if(vec.at(left) == vec.at(right)){ left++; continue; }

        /* Do the normal swapping */
        int temp = vec.at(left);
        vec.at(left) = vec.at(right);
        vec.at(right) = temp;
    }
    return right;
}


/* Returns the k-th element of this array. */
int MoM(vector<int>& vec, int k, int start, int end){
    /* Start by base case: Sort if less than 10 size
     * E.x.: Size = 9, 9 - 0 = 9.
     */
    if(end-start < 10){
        sort(vec.begin()+start, vec.begin()+end);
        return vec.at(k);
    }

    vector<int> medians;
    /* Now sort every consecutive 5 */
    for(int i = start; i < end; i+=5){
        if(end - i < 10){
            sort(vec.begin()+i, vec.begin()+end);
            medians.push_back(vec.at((i+end)/2));
        }
        else{
            sort(vec.begin()+i, vec.begin()+i+5);
            medians.push_back(vec.at(i+2));
        }
    }

    int median = MoM(medians, medians.size()/2, 0, medians.size());

    /* use the median to pivot around */
    int piv = pivot(vec, median, start, end);
    int length = piv - start+1;

    if(k < length){
        return MoM(vec, k, start, piv);
    }
    else if(k > length){
        return MoM(vec, k-length, piv+1, end);
    }
    else
        return vec[k];
}

- OneRaynyDay