求中位數

對本題感興趣的原因是覺得與 LeetCode 4. Median of Two Sorted Arrays 有關，以為先練成求單一陣列中位數，會比較知道求兩個陣列的中位數該怎麼做(不過這樣的線性思考似乎沒什麼用...)

在冼鏡光老師的 C 名題精選百則，問題 5-6 求中位數裡已經有詳細解答。但筆者在研究該解答時發現一件怪事，在大量測試下，有時得出的中位數與排序後得到的中位數不一樣。

下面為測試程式，與冼老師解答使用的演算法 100% 一樣(5-24頁)，只是改用 C++ 實作：

#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace::std;

void swap(int& a, int& b)
{
    const int tmp = a;
    a = b;
    b = tmp;
}

void split(vector<int>& v, int first, int last, int& split_point)
{
    const int split_data = v[first];
    split_point = first;
    for(int i = first + 1; i <= last && split_point <= last; ++i)
    {
        if(v[i] < split_data)
        {
            ++split_point;
            swap(v[split_point], v[i]);
        }
    }

    swap(v[first], v[split_point]);
}

int median(vector<int>& v)
{
    int left = 0;
    int right = v.size() - 1;
    const int middle = (left+right)/2;
    int split_point;
    while(1)
    {
        split(v, left, right, split_point);
        if(split_point == middle)
            break;
        else if(split_point > middle)
            right = split_point - 1;
        else
            left = split_point + 1;
    }
    
    if((v.size()%2) != 0)    
        return v[middle];
    else
        return (v[middle]+v[middle+1])/2; 
}

int main(int argc, char *argv[])
{
    using namespace::std;
    
    srand(time(0));
    for(int i = 0; i < 10000; ++i)
    {

        vector<int> v;
        while(v.size()==0)
            v.resize(rand()%1000);

        for(size_t i = 0; i < v.size(); ++i)
            v[i] = rand();

        vector<int> v2 = v;
        int median1 = median(v);

        sort(v2.begin(), v2.end());
        const int middle = (v2.size() - 1)/2;
        int median2;
        if((v2.size()%2) != 0)
            median2 = v2[middle];
        else
            median2 = (v2[middle]+v2[middle+1])/2;

        if(median1 != median2)
        {
            printf("median1=%d,median2=%d\n", median1, median2);
            printf("oops!\n");            
            break;
        }
    }
    
    return 0;
}

程式的精髓是 Line 7. split()，以三步驟將陣列劃分：

Step 1.

Step 2.

Step 3.

接著，Line 41-46 依據 < split_data 與 >= split_data 哪塊比較長來決定如何調整 left 或 right，如果 Line 40 取得的 split_point 等於 middle，則中斷 Line 38. while loop，得到答案。

後來找了很久，才知道要等 left 與 right 交會時中斷 Line 38. while loop 才是對的，程式修改如下：

int median(std::vector<int>& v)
{
    //...
    while(1)
    {
        split(v, left, right, split_point);
        if(left >= right)
            break;
        else if(split_point > middle)
            right = split_point - 1;
        else
            left = split_point + 1;
    }
        
    //...
}

至於「為什麼？」筆者也還在思考中，只能說演算法真的是很深奧的學問，寫出程式還不是最難的，要證明一隻程式 100% 正確無誤很難...