兩個等長有序數組求中位數

在網上看了很多兩個等長有序數組求中位數的文章，但我都覺得有點兒問題。等下會說我覺得問題在哪裡。

先說下中位數定義：當數組元素個數為奇數個的時候，中位數就是中間的數字，比如數組[1,2,3,4,5]，那麼3就是中位數。如果數組元素個數為偶數個的時候，那麼中間兩個元素的平均值就是中位數的值，比如數組[1,2,4,5]，那麼中位數就是(2+4)/2=3.

定義清楚了下面就來說下兩個等長數組求中位數的問題，為了簡化問題，直接假設兩個數組都按從小到大順序排列好了。兩個等長數組，那麼總的元素個數肯定為偶數，那麼結果就肯定是某兩個數字的平均值。

求解方法基本都一樣，就是用二分搜尋的思路來做。假設有兩個數組A，B，首先用兩個指針a，b分别指向A，B中間的數字，然後比較這兩個數字，假設a指向數字大于b的數字，那麼結果肯定不在a指向數字的右邊和b指向數字的左邊。然後分别向左向右移動a，b兩個指針，再次進行比較。就是二分搜尋的思路。

然後說問題，在網上看了好多部落格，求得的結果都是指針移動的最後結果是A中某一進制素和B中某一進制素一起作為結果。但我認為這是不對的，因為最終結果的兩個數字完全可以在同一個數組中，假設有兩個數組

A：1 2 7 9 10

B：3 4 5 6 8

合并後中位數應該是5 和 6，兩個數都在數組B中，并不是A、B各一個數。

網上很多人寫的疊代結束條件都是找到了a=b或者最後子數組長度都為1，我覺得結束條件應該是找到a=b或者數組長度為2。

可能對于這個問題有點兒鑽牛角尖了，思路大家基本都差不多，隻是我在疊代的結束條件上和大家看法不太一樣，也許我考慮的有問題，希望各位批評指正。

以下是實作代碼：

#include <stdio.h>

void findMedian(int first[],int second[],int length);

int result[4];//因為是疊代為2的時候結束，是以會有4個數字對于四個數字應該還排下序，然後取中間兩個，這裡直接列印輸出

int main(void){

int first[]={1,2,3,6,11};

int second[]={4,7,8,10,12};

findMedian(first,second,5);//随便寫的兩個數組例子

printf("%d  %d  %d  %d\n",result[0],result[1],result[2],result[3]);//

}

void findMedian(int first[],int second[],int length){

if(length<=2){

result[0]=first[0];

result[1]=first[1];

result[2]=second[0];

result[3]=second[1];

}

int low1=0,low2=0,high1=length-1,high2=length-1;

int current1,current2,k1,k2;

while(length>2){

current1=(low1+high1)/2;

current2=(low2+high2)/2;

if(first[current1]==second[current2]){

printf("The median is %d\n",first[current1]);

 //因為主函數中有輸出，是以這裡就賦了下值

result[0]=first[current1];

result[1]=first[current1];

result[2]=first[current1];

result[3]=first[current1];

return;

}

else if(first[current1]>second[current2]){

//k1 k2表示目前指針和邊界的距離，因為存在奇偶問題，是以k1和k2不一定相同，指針移動時候要移動二者中較小的距離

k1=high1-current1;

k2=current2-low2;

if(k1==k2){

high1=current1;

low2=current2;

length-=k1;

}

else if(k1>k2){

high1=current1+1;

low2=current2;

length-=k2;

}

else{

high1=current1;

low2=current2-1;

length-=k1;

}

}

else{

k1=current1-low1;

k2=high2-current2;

if(k1==k2){

high2=current2;

low1=current1;

length-=k1;

}

else if(k1>k2){

low1=current1-1;

high2=current2;

length-=k2;

}

else{

high2=current2+1;

low1=current1;

length-=k1;

}

}

}

result[0]=first[low1];

result[1]=first[high1];

result[2]=second[low2];

result[3]=second[high2];

}