4-寻找两个正序数组的中位数

题目给定了两个正序数组 A、B，长度分别为 m，n。

求两个正序数组的中位数：

根据算法复杂度的要求，大概能够想到使用二分法。

对两个数组同时使用二分搜索，我们可以划分出 aMid 和 bMid，并且两个数组对应的中位数的值分别是 aVal 和 bVal。

从上图可以看出，aMid 和 bMid 将数组分成了四个部分 a、b、c、d，

其中 a 和 b 的数组长度都是 m/2，c 和 d 的数组长度都是 n/2。

明确一点：最终需要的中位数，应该刚好由 (m + n) / 2 或 (m + n) / 2 + 1 决定。

假设 aVal > bVal，将两个数组进行如下的简单拼接：

由图片，可以看到 aVal 右边的区域（b 区域）总是大于 bVal 左边的区域（c 区域）的。

假设中位数在 c 区域，那么在 a 区域中所有的元素都要小于 bVal，

这样才能导致 n/2 + (m - 1) /2 = (n + m - 1) / 2，但是依然无法满足中位数的条件。因为 aVal > bVal。

假设中位数在 b 区域，由于 b 区域永远位于 A 数组的右边，并且永远大于 aVal，

想要 m/2 趋向 (n + m) /2，则需要让 d 区域所有元素都是大于 aVal，

但是即使满足了，依然只是满足了 (n+m -1) /2，也不是中位数。

由此可以排除c b两个区域。