题目描述
思路解析
一句话答案：不要真的合并两个数组。把中位数看成一条分界线：线左边放一半元素，且左边最大值不大于右边最小值；然后只在较短数组的切口上二分。
为什么归并法不够
归并能得到正确中位数，但要扫描 m+n 个元素，时间是 O(m+n)。本题明确要求 O(log(m+n))，所以归并只能当朴素思路或对拍方法，不能当主解。
对数复杂度意味着每轮必须排除一半候选。真正可二分的对象不是某个数，而是较短数组的 m+1 个切口。
合法切口只有两个条件
设 A 较短，在 A 中切 i 个元素到左边；为了让左半元素数等于 (m+n+1)/2，B 的切口只能是 j=half-i。
数组内部已经有序，因此只需检查跨数组关系：Aleft≤Bright 且 Bleft≤Aright。两条都成立，左半所有元素就都不大于右半。
二分方向怎么判断
若 Aleft>Bright，A 放进左半的元素太多，i 要左移。否则若 Bleft>Aright，A 放得太少，i 要右移。每次都能丢掉一半切口。
切口落在数组首尾时，用 -∞ 或 +∞ 表示不存在的边界。这样空数组、全切到左边、全留在右边都能用同一套判断。
怎样从切口读中位数
总长度为奇数时，左半多一个元素，中位数是 max(Aleft,Bleft)。总长度为偶数时，中位数跨在切口两侧，答案是 (max(Aleft,Bleft)+min(Aright,Bright))/2。
搜索只发生在较短数组上，所以时间复杂度是 O(log(min(m,n)))，额外空间是 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
目标从“合并数组”换成“找到合法切口”：左边数量正确，而且左边每个数都不大于右边。
A 切 i 个、B 切 j 个到左边。j 由总左半长度减 i 自动得到，所以真正需要搜索的只有 i。
A 更短，所以只在 A 的 0 到 5 号切口里二分。总长 11，左半应该放 6 个数。
第一轮先由 lo 和 hi 算出 i=2，再由左半固定容量算出 j=4；两个切口不是独立猜出来的。
先试 A 的中间切口 i=2，B 就要切 j=4，左半总数才是 6。四个边界值决定这刀是否正确。
把 B 的切口单独展开：前四个数进入左半，切口两侧是 19 和 21。现在四个边界值已经齐全。
交叉检查发现 19 越过了 8，说明 A 留在左半的元素太少；失败条件直接决定下一步向右搜索。
B 左边的 19 跑到了 A 右边 8 的前面，说明 A 切得太少。把 i 向右推，下一轮从 3 开始找。
因为 i≤2 都会让 A 的右边界不够大，可以一次排除三个切口；这就是对数复杂度真正发生的地方。
A 上只剩切口 3、4、5。二分不是移动数组，而是在 m+1 个切口组成的有序搜索空间里持续砍半。
新区间是 [3,5]，中点 i=4；对应 j=2。再次只看切口左右的四个数，不用合并任何元素。
第二轮 i=4 时，j 自动变为 2；B 左半只留下 7、11，切口边界变成 11 和 18。
这次两条交叉不等式同时成立；数组内部本来有序，因此四个边界已经足以证明整个左半不大于整个右半。
两条交叉不等式都成立，说明左半所有数都不大于右半。合法切口已经找到。
合法划分同时满足数量与顺序两项条件。到这里不用知道左右半内部完整排序，也能直接读取中位数。
总长是奇数时，左半比右半多一个元素，中位数就是左半最大值 11。
偶数总长时，中位数跨在切口两侧，所以取左半最大值与右半最小值的平均。
再走一个偶数总长例子：A=[1,2] 在 i=1 处切开，切口两侧为 1 和 2。
若直接使用 i=1、j=1，会发现 Bleft=3 大于 Aright=2，说明 A 切得太少，还需要向右移动。
把 A 的切口右移到末尾 i=2，B 的切口随之变为 j=0；哨兵让数组端点仍可使用同一组比较。
偶数长度在合法切口两侧各取一个边界：左半最大 2、右半最小 3，平均后得到 2.5。
四类边界都由同一组哨兵处理，不需要给空数组、全在左边或全在右边分别写分支。
面试时把证明说成两句话：数量正确，顺序正确。数量由 half 保证，顺序由两条交叉不等式保证。
参考代码
class Solution: def findMedianSortedArrays(self, A, B): if len(A) > len(B): return self.findMedianSortedArrays(B, A) m, n = len(A), len(B) lo, hi = 0, m half = (m + n + 1) // 2 while lo <= hi: i = (lo + hi) // 2 j = half - i al = float('-inf') if i == 0 else A[i - 1] ar = float('inf') if i == m else A[i] bl = float('-inf') if j == 0 else B[j - 1] br = float('inf') if j == n else B[j] if al <= br and bl <= ar: if (m + n) % 2: return max(al, bl) return (max(al, bl) + min(ar, br)) / 2.0 if al > br: hi = i - 1 else: lo = i + 1复杂度
- 时间：O(log(min(m,n)))，只在较短数组的 m+1 个切口上二分
- 空间：O(1)，只保存边界和切口变量，不创建合并数组
易错点
面试追问把动画讲成自己的话
追问怎样证明合法切口给出的就是中位数？
追问为什么条件只检查 Aleft≤Bright 和 Bleft≤Aright？
追问归并法还有价值吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
查找元素的首末位置
LeetCode 34 · 中等 · 沿着 二分查找 继续往下推进