> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/introduction-3/exercise/9.3-8.md).

# 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个元素求中位数。

## 三、代码

[产品代码](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/src/chapter9/Exercise9_3_8.cpp)\
[测试代码](https://github.com/windmissing/exerciseForAlgorithmSecond/blob/master/tst/cases/Exercise9_3_8Test.cpp)