算法导论 9.3-8 求两个数组的中位数

设X[1..n]和Y[1..n]为两个数组，每个都包含n个已排好序的数，给出一个求数组X和数组Y中所有2n个元素的中位数的O(lgn)时间的算法

递归求解该问题，解题规模不断减半，最后剩下4个元素时，得到问题的解，

本文求的是下中位数，下中位数的特点是：

（1）当n为奇数，令n = 2 * m + 1，下中位数是第m+1小的数，数组中有m个数小于下中位数，有m个数大于下中位数。当数组中的一个数满足以下特点中的任意一个时，认为该数不是下中位数：a.至少有m+1个数比x大b.到少有m+1个数比x小

（2）当n为偶数，令n = 2 * m，下中位数是第m+1小的数，数组中有个m个数小于下中位数，有m-1个数大于下中位数。当数组中的一个数满足以下特点中的任意一个时，认为该数不是下中位数：a.至少有m个数比x大b.到少有m+1个数比x小

令Na为数组A中元素的个数，Nb为数组B中元素的个数，Ma是数组A中的下中位数，数组Mb是B中的下中位数，a=Na/2，b=Nb/2 。它们满足以下关系

（1）Na和Nb初始时相等，经过对数组的处理后，依然相等，奇偶性相同，同理a和b也始终相等

（2）Ma和Mb的大小不确定，本文例举了Ma>Mb的处理方法

可以把问题分为以下两种情况：

（1）Na和Nb都是偶数，令Na=2*a，Nb=2*b，a=b，Ma>Mb（初始情况）

分析：

在数组A中有a个数字小于Ma，有a-1个数字大于Ma

在数组B中有b个数字小于Mb，有b-1个数字大于Mb

Ma>Mb =====> 大于Ma的数字都大于Mb，小于Mb的数字都小于Ma

=====> A和B中至少有a+b+1个数字小于Ma，至少有a+b-1个数字大于Mb

=====>所有大于Ma（不包括Ma）的数字都不是中位数，所有小于Mb（不包括Mb）的数字都不是中位数

=====>A[1..Na] -> A[1..a+1]，B[1..Nb] -> B[b+1..Nb]

（2）Na和Nb都是偶数，令Na=2*a+1，Nb=2*b+1，a=b，Ma>Mb（初始情况）

分析：

在数组A中有a个数字小于Ma，有a个数字大于Ma

在数组B中有b个数字小于Mb，有b个数字大于Mb

Ma>Mb =====> 大于Ma的数字都大于Mb，小于Mb的数字都小于Ma

=====> A和B中至少有a+b+1个数字小于Ma，至少有a+b+1个数字大于Mb

=====>所有大于Ma（不包括Ma）的数字都不是中位数，所有小于Mb（包括Mb）的数字都不是中位数

=====>A[1..Na] -> A[1..a+1]，B[1..Nb] -> B[b+1..Nb]

经过上文中的分析，最终算法过程如下：

Step1：分别求出两个数组的中值midA和midB，比较midA和midB的大小

Step2：如果midA=midB，那么这个值就是这（nA+nB）个数中的中位数

Step3：如果midA < midB，A[1..Na] -> A[a+1..Na]，B[1..Nb] -> B[1..b]，递归地对两个新的数组求中位数。

Step4：如果midA > midB，A[1..Na] -> A[1..a]，B[1..Nb] -> B[b+1..Nb]，递归地对两个新的数组求中位数。

Step5：反复Step1-Step4中的递归操作，直到两个数组剩下的元素一共不超过4个，直接对这4个元素求中位数。

产品代码测试代码可以用git下载、更新、提交、评论代码