9.3-8 设X[1..n]和Y[1..n]为两个数组，每个都包含n个有序的元素，请设计一个$O(lgn)$时间的算法找出数组X和Y中所有2n个元素的中位数。 下面假设中位数(低中位数，数组长度偶数时较小的那个)在数组$X$中。如果要求中间两个数的均值，只需要在该基础之上修改一点就好。
a、$X[k]=m$为中位数，对于数组$X$,有$k$个元素小于等于$X[k]$，同时有$n-k$个元素大于等于$X[k]$。当两个数组合并有序时，对于中位数来说，共有$n$个元素小于等于$X[k]$，n个元素大于等于$X[k]$。那么对于数组$Y$来说，有$n-k$个元素小于等于$X[k]$，$n-(n-k)=k$个元素大于等于$X[k]$。那么就存在以下不等式：
b、$若X[k]$不是中位数。且中位数为$X[k’] \,(1 \leq k’ < k < n)$，那么就有：
那么对于$X[k]$来说，有：
c、$若X[k]$不是中位数。且中位数为$X[k’] (1 \leq k < k’ < n)$，那么就有：
那么对于$X[k]$来说，有：
d、在递归的过程中，我们要注意一个递归的一个边界问题，在实际的编程中，对于数组$A[L,..R]，1 \leq L \leq R \leq n$。我们取$k=(L+R)/2,k \in [1,n]$, 当$k=n$时，那么对于上面三种情况会出现$Y[n-k]=Y[0]$是一个空数组，对于这种情况，其实只需判断$X[k]=X[n] \leq Y[1]$。
利用上面的性质，就可以在$O(1)$的时间内判断$X[k]$是否时中位数。对于一个数组区间$X[L,R]$。我们采用二分的思想，取中点$k=(L+R)/2$，判断上面的条件，如果满足条件a或d，那么$X[k]$就是中位数，如果是条件b，那么说明$k$偏大，我们在左子区间继续二分查找，否则为条件c，我们在右子区间继续二分查找。这样的一个二分查找过程的时间复杂度为$\Theta(lgn)$。
上面给出性质的是假设中位数在数组$X$的分析，如果中位数不在数组$X$中，在查找的过程中到达边界而不满足$X[k]$为中位数的a条件，我们可以返回一个标志如NOTFIND。此时中位数一定在数组$Y$中，我们进行同样的操作。最差情况下进行$2lgn$次查找。时间复杂度仍为为$\Theta(lgn)$。
下面是伪代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Two-Array-Medium(X,Y) n <-- X.length medium = Find-Medium(X,Y,1 ,n,n) if medium = NOTFIND medium = Find-Medium(Y,X,1 ,n,n) return mediumFind-Medium(A,B,low,high,n) if low > high return NOTFIND else k = (high+low)/2 if k=n and A[n]<=B[1 ] return A[n] elseif k < n and B[n-k] <= A[k] <= B[n-k+1 ] return A[k] elseif B[n-k+1 ] < A[k] return Find-Medium(A,B,low,k-1 ,n) else return Find-Medium(A,B,k+1 ,high,n)
实际编程中，数组从0开始稍微改动下即可。
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 #include <iostream> #include <ctime> #include <random> #include <algorithm> using namespace std ;#define LEN 5 #define NOTFIND 0x3f3f3f3f int findMedium (int A[],int B[],int L,int R,int n) if (L>R) return NOTFIND; int k=(L+R)/2 ; if (k==(n-1 )&&A[k]<=B[0 ]) return A[k]; else if (k<(n-1 )&&B[n-k-2 ]<=A[k]&&A[k]<=B[n-k-1 ]) return A[k]; else if (B[n-k-1 ]<A[k]) return findMedium(A,B,L,k-1 ,n); else return findMedium(A,B,k+1 ,R,n); } int TwoArrayMedium (int A[],int B[],int len) int ret=NOTFIND; if ((ret=findMedium(A,B,0 ,len-1 ,len))==NOTFIND) ret=findMedium(B,A,0 ,len-1 ,len); return ret; } template <typename T,unsigned N>void getRandomArray (T (&arr)[N]) static default_random_engine e (time(nullptr )) static uniform_int_distribution<T> d(0 ,2000 ); for (auto &i:arr) i=d(e); sort(arr,arr+N); } int main () int A[LEN]; int B[LEN]; getRandomArray(A); getRandomArray(B); int C[2 *LEN]; copy(A,A+LEN,C); copy(B,B+LEN,C+LEN); sort(C,C+2 *LEN); for (auto i:C) cout << i << " " ; cout << endl ; cout << "中位数为:" << TwoArrayMedium(A,B,LEN) << endl ; return 0 ; }
这个问题我只求了低中位数，因为数组总长度为$2n$恒为偶数，因此如果要求中间两个数的均值。只需要在上面代码的基础上稍微改下，加上$k+1$位置的数，然后除2即可达到。（注意：如果k求出是X数组的最后一位，那么高中位数在数组Y中） 。
