计算两个数组X和Y所有元素的中位数

算法导论第三版，9.3-8

算法：

1. 当两个数组的长度均为1时，选取其中数值较小的那个元素
2. 若非如此，则分别从两个数组中提取各自的中位数
3. 将具有较大中位数的数组的前半部分与中位数较小的数组的后半部分进行组合，形成一个长度为n的新数组
4. 随后确定该新数组的中位数

思路：
采用递归分治策略时，必然存在基础情形。当数组长度缩减至1时，即为该基础情形。
通过观察可以发现，整体的中位数必定处于两个原始数组各自中位数之间。具体证明过程如下：
假设整体的中位数为M，设X的中位数为M_X，而Y的中位数为M_Y。若假设某元素位于特定位置，则其在整体中的坐标可表示为k。

1. 在合并后的集合X+Y中共有n个元素小于或等于该值，其中来自某一集合的部分贡献了若干个元素，另一部分则贡献了n-k个元素。

   • 在某一子集中有n/2个元素小于或等于该值，在另一子集中则有相应数量的小于关系成立
   • 基于上述两点分析可知，若k < n/2，那么将出现特定的关系式：M_Y MYX