9.3-8 设X[1..n] 和 Y[1..n]为两个数组，每个都包含n个已排好序的数。给出一个求数组X和Y中所有2n个元素的中位数的O(lgn）时间的算法
分析与解答：
若中位数位于X中，不妨设为X[k]，即在X中有k个元素小于等于中位数，n-k个元素大于等于中位数。由于X[k]为合并后的2n个元素的中位数，则在Y中有n-k个元素小于等于中位数，k个元素大于等于中位数，即
Y[n-k] ≤ X[K] ≤ Y[n-k+1]
看到时间复杂度为O(lgn)，不禁使我们想到二分法，但是和这题有什么关联呢？
二分法每次搜索都能减小一半的范围，在搜索中位数的过程也可以的，下面具体论述:
若X[k]不满足上述等式，分两种情况
(1) X[k] < Y[n-k]
若中位数是k' < k，则X[k'] ≤ X[k]] < Y[n-k] 。那么在Y中小于等于X[k']的元素数目小于n-k，则X[k']不可能为中位数
由此只需要搜索k' > k的范围
(2) X[k] > Y[n-k+1]
若中位数是k' > k，则X[k'] > X[k] > Y[n-k+1] 。那么在Y中小于等于X[k']的元素数目大于n-k+1，则X[k']不可能为中位数
由此只需要搜索k' < k的范围
根据上述特点，我们可以采用二分搜索逐步缩小搜索范围。
整个算法的过程如下：