两个有序数组的中位数为什么能用二分做到 O(log(m+n))？

简化版

两个有序数组中位数的高阶解法是在较短数组上二分“分割线”。设左半部分总长度为 (m+n+1)/2，在 A 中切 i 个，在 B 中切 j=half-i 个。若 Aleft <= Bright 且 Bleft <= Aright，说明左右分割合法，中位数由左半最大值和右半最小值决定；否则根据哪边太大移动 i。复杂度 O(log min(m,n))。

详细版

目标是找到一个分割，使得左半元素个数等于右半或多一个，并且左半所有元素都不大于右半所有元素。因为 A、B 各自有序，只需检查交叉边界：A[i-1] <= B[j] 和 B[j-1] <= A[i]。为了避免越界，边界外用 -inf/+inf 表示。

double findMedianSortedArrays(int[] A, int[] B) {
    if (A.length > B.length) return findMedianSortedArrays(B, A);
    int m = A.length, n = B.length;
    int half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;
        int j = half - i;
        int Aleft = i == 0 ? Integer.MIN_VALUE : A[i - 1];
        int Aright = i == m ? Integer.MAX_VALUE : A[i];
        int Bleft = j == 0 ? Integer.MIN_VALUE : B[j - 1];
        int Bright = j == n ? Integer.MAX_VALUE : B[j];
        if (Aleft <= Bright && Bleft <= Aright) {
            if (((m + n) & 1) == 1) return Math.max(Aleft, Bleft);
            return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.0;
        } else if (Aleft > Bright) hi = i - 1;
        else lo = i + 1;
    }
    return -1;
}

这题难点在分割线含义，不在代码长度。必须在较短数组上二分，保证 j 不越界，并减少复杂度。

完整版教学

一、先把中位数转成左右分割问题

两个有序数组合并后，中位数位于整体中间。真正需要的不是完整合并数组，而是知道左半最大值和右半最小值。因此可以把问题改写成：在 A、B 中各切一刀，让左边元素数量达到中位数所需数量，并且左边所有元素都不大于右边所有元素。

例如 A=[1,3]，B=[2]，总长度 3，左半应有 (3+1)/2=2 个元素。若 A 切 1 个、B 切 1 个，左半是 [1,2]，右半是 [3]，中位数就是左半最大值 2。这个分割视角避免了 O(m+n) 合并。

A: [1 | 3]
B: [2 | ]
left size = 2, right size = 1
median = max(left) = 2

二、为什么只检查四个边界值

A 和 B 本身已经有序，所以 A 左边一定不大于 A 右边，B 左边一定不大于 B 右边。要保证整体左半不大于整体右半，只需要检查交叉关系：A 左边最大值是否不大于 B 右边最小值，B 左边最大值是否不大于 A 右边最小值。

这就是两个条件：Aleft <= Bright 和 Bleft <= Aright。一旦成立，左半所有元素都小于等于右半所有元素。没有必要检查左半里的每个元素，因为各自数组内部有序已经替你完成了大部分证明。

条件	含义
`Aleft <= Bright`	A 左侧不会越过 B 右侧
`Bleft <= Aright`	B 左侧不会越过 A 右侧

记忆钩子：两个数组各自有序，所以合法分割只看“交叉的四个门卫”。

三、为什么在较短数组上二分

设 A 长度为 m，B 长度为 n。我们枚举 A 左侧取多少个元素 i，那么 B 左侧数量 j=half-i 就被确定。为了让 j 始终可能落在 [0,n] 内，通常把较短数组放在 A 上二分。这样 i 的范围更小，复杂度也是 O(log min(m,n))。

如果在较长数组上二分，某些 i 会导致 j 为负或超过 B 长度，需要额外处理，代码更容易错。把短数组放前面是一种降低边界复杂度的工程技巧。它不改变数学本质，但能明显提高实现稳定性。

if (A.length > B.length) swap(A, B)
i in [0, m]
j = half - i

四、二分方向怎么判断

如果 Aleft > Bright，说明 A 左边拿多了，A 的切口太靠右，需要减少 i，所以 hi = i - 1。如果 Bleft > Aright，说明 A 左边拿少了，导致 B 左边过大的元素压到左半，需要增加 i，所以 lo = i + 1。

带例子：A=[1,2,8]，B=[3,4,5,6,7]，若 i=2，j=2，则 Aleft=2、Aright=8、Bleft=4、Bright=5，条件成立吗？Bleft <= Aright 成立，Aleft <= Bright 也成立，分割合法。若 i=3，Aright=+inf、Aleft=8、Bright=4，Aleft > Bright，说明 A 取太多。

Aleft > Bright -> i 太大 -> 左移
Bleft > Aright -> i 太小 -> 右移

五、奇偶长度如何返回答案

如果总长度是奇数，左半比右半多一个元素，中位数就是左半最大值 max(Aleft, Bleft)。如果总长度是偶数，中位数是左半最大值和右半最小值的平均，即 (max(left) + min(right)) / 2。

为什么 half=(m+n+1)/2 要加 1？这样奇数时左半自然多一个元素，返回左半最大值即可。比如总长度 5，half=3；总长度 4，half=2。这个统一写法减少了奇偶分支里的下标混乱。

odd:  median = max(Aleft, Bleft)
even: median = (max(Aleft,Bleft) + min(Aright,Bright)) / 2

六、边界哨兵避免越界

当 i=0 时，A 左边没有元素，Aleft 可以视为负无穷；当 i=m 时，A 右边没有元素，Aright 可以视为正无穷。B 也同理。使用哨兵值后，分割在数组两端的情况也能用同一套条件判断。

例如 A 为空、B=[1,2,3]，A 的左右都是哨兵，最终答案完全来自 B。没有哨兵时，你需要写很多 if 分支；有哨兵时，代码更短，但要注意数据范围。如果数组元素可能达到 Integer.MIN_VALUE/MAX_VALUE，理论上可用 long 哨兵或单独判断。

切口位置	左边界	右边界
i=0	-inf	A[0]
0<i<m	A[i-1]	A[i]
i=m	A[m-1]	+inf

七、常见误区与追问

误区：必须先合并数组。 合并是 O(m+n)，题目高阶要求是通过分割做到对数复杂度。
误区：在任意数组上二分都一样。 在较短数组上二分能减少边界风险，并得到 O(log min(m,n))。
误区：只比较 Aleft 和 Aright。 A、B 内部本来有序，关键是交叉边界 Aleft/Bright 与 Bleft/Aright。
追问：为什么 half 要写 (m+n+1)/2？ 让奇数长度时左半多一个元素，中位数统一取左半最大。
追问：如果一个数组为空怎么办？ 哨兵边界可自然处理，答案退化为另一个有序数组的中位数。
追问：为什么 Aleft > Bright 时 i 要左移？ A 左边拿了太多大元素，减少 i 才能让 Aleft 变小。

八、加强记忆

这题不要想着“合并”，要想着“切两刀”。左半数量固定为 half，A 切 i，B 切 half-i。合法分割只看四个边界：Aleft <= Bright 且 Bleft <= Aright。合法后，奇数取左半最大，偶数取左半最大和右半最小的平均。二分的是短数组里的切口位置。

简化版

详细版