【问题】给定两个长度都为N的有序数组X和Y，写一个函数来找到X和Y合并后的数组的中位数。

【解答】：

首先明确一点，因为X和Y长度一样，所以中位数肯定是有两个的，左中位数和右中位数。

现在我们的思路是，要不断缩小两个数组的长度，同时保证那两个中位数总是在两个数组中，当两个数组的长度足够小的时候，我们就可以轻易找到答案了。

为了方便叙述，我们假定我们可以对数组的每个元素染色，染成黑色或者白色。

假设左右中位数分别为a,b。那么，我们把X和Y中所有小于等于左中位数的数都染成白色，把所有大于等于右中位数的数染成黑色。

由于X和Y是有序的，所以X和Y它们的颜色都必定是一串白接着一串黑，而且X里的白色数的个数等于Y里的黑色数的个数，这一点画个图就清楚了。

假设N是奇数，那么我们取出X的中位数x，和Y的中位数y，那么，x和y必然其中一个为白色另一个为黑色（画个图就明白了），又因为黑色数必定比白色数大，所以我们只要比较一下x和y的大小，我们就可以分辨出哪个是黑色哪个是白色。然后，我们把白色的数前面的数全部删掉，把黑色那个数后面的数全部删掉，这样子，我们就成功删掉了同样个数的白数和黑数，删掉同样的黑数和白数并不会改变剩下的X和Y的中位数。

这里有个问题，为什么我们不能删掉这一步的x和y，既然它们也是一个白一个黑，因为我们删数一定要保证我们不会连我们要找的那2个中位数也删掉。不妨让x是白色，y是黑色，因为左中位数是所有白色数里最大的那一个，所以比x小的那些白色数都不可能是左中位数，所以我们删掉它们，但是x还是有可能就是左中位数的，所以我们不能删。y的部分同理。

假设N是偶数，那么我们取出X的左中位数x和Y的右中位数y，可以证明，任何情况下，x和y必然其中一个为黑色另一个为白色（画个图就明了了）。所以，我们还是可以通过比较x和y的大小来分辨出它们的颜色，然后和上面的做法一样，我们删掉同样数量的白数和黑数。

我们递归地利用剩余的X和Y来做删数的操作，直到由于删除的数总是开头或者结尾的连续一段，所以其实不需要删，只要变一下首尾下标就可以了。由于每次删除的数为当前数组长度的1/2，所以时间复杂度是O(logN)