设两个数组中位数为 ， 可将两个数组分别划分为两半：

其中

这里先不关注 、 在边缘情况的取值问题，稍后再详细说明。

如果同时满足以下两个条件：

2. 左边最大的元素 ，右边最小的元素

则找到了划分位置，并且

由此，问题转化为：查找这样的 ，且同时满足以上两个条件，即可得出中位数 。

根据第一个条件，由 和 之间的关系，在编程语言中可以直接根据 计算得出 ：

1

j = (m + n + 1) / 2 - i;

以上表达式在 奇偶情况下均成立。

第二个条件等价于：

现考察 的范围，先将 表示为

显然 随 递增而递减，只需 即可，又，则：

即可保证 。

• 当 为偶数时，，则

• 当 为奇数时，，则 ，又 、 必为一奇一偶，因此

综合得

因此只需 ，即保证 。

在编程实现时，就要先比较两个数组长度，如果 ，就要将两个数组交换。

要在 中查找合适的 ，自然联想到二分查找。

初始情况下，令

1

int begin = 0, end = m;

然后令

1
2

i = begin + (end - begin) / 2;
j = (m + n + 1) / 2 - i;

如果m == 0，此时相当于只对 数组进行划分，直接找到了 、 的值。

如果m != 0，就要判断上面第二个条件是否成立，成立则找到所求划分位置，否则就舍去 到 一半的元素，然后继续查找。

但是在的判断中可能会有 、、、 不存在的情况，又需要进一步讨论。

我这里给出的方法比较笨，分为如下三种情形，如果你有更好的方法欢迎讨论：

• 时

  不存在，相当于把数组 的所有元素划分到右边，只需判断 是否成立即可。

  但 是否存在，也就是说是否一定有 呢？答案是肯定的。显然 ，注意到 是一个恒定的正数(m + n + 1) / 2，因此 ， 。

  这样，

  • 若 ，说明 太小， 的最终位置应在 之中，此时就应舍去一半元素：

  1	begin = i + 1;

  • 否则说明找到

• 时， 在 、 处分别取 、，则 。

  此时两个不等式中的元素均存在，并且

  • 若 ，说明 太小， 太大，应：

    1	end = i - 1;

  • 若 ，说明 太小，应：

    1	begin = i + 1;

  • 否则说明找到

• 时

  不存在，只需判断 是否成立即可。显然 必存在，又 ，故 也必存在。

  在这种情况下，

  • 若 ，说明 太大，应：

    1	end = i - 1;

  • 否则说明找到

这样，通过二分查找，找到所需要的 的值。

现在已经找出了划分位置，如果共有奇数个元素，则中位数为左边元素的最大值，如果共有偶数个元素，则中位数为左边最大值和右边最小值的平均数。

• 若 不存在，即 ，左边最大值即为 （ 为确定的正数(m + n + 1) / 2，故 ， 必定存在）

• 若 不存在，即 ，左边最大值即为 （同样 必定存在）

• 若 、 均存在时，左边最大值为

如果 为奇数，则直接返回左边最大值，否则同理求得右边最小值，返回它们的平均数。

此算法相当于在长度为 的数组 中进行二分查找，由于保证了 ，因此时间复杂度为 。