求中位數

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

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

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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

#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 才是對的，程式修改如下：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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% 正確無誤很難...