97.寻找两个正序数组的中位数
题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
- 输入：nums1 = [1,3], nums2 = [2]
- 输出：2.00000
- 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
- 输入：nums1 = [1,2], nums2 = [3,4]
- 输出：2.50000
- 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
思路
最简单的办法：把两个列表合并成一个，然后找中位数。
但如果每个店都有几百万条数据呢？合并太慢了，我们需要更聪明的办法。
什么是中位数？
-
如果总长度是奇数：最中间的那个数
-
如果总长度是偶数：最中间两个数的平均值
最笨的方法，就是把两个数组合并成一个，然后找中间那个数。 这个办法的时间复杂度是O(m+n)，因为你要遍历所有元素才能合并。
但是我们真的需要合并所有元素吗？
不需要！ 我们只需要合并到中间位置就可以了。
比如总长度是8，中间位置是第4个和第5个，我们只需要合并到第5个就可以停了。
中位数 = (第4个的值 + 第5个的值) / 2
这个办法的时间复杂度是O((m+n)/2)，比刚才好了一点，但是还不够快。
核心问题 -- 能不能更快
假设数据非常大，比如每个数组有100万个元素。
用上面的方法，我们需要走50万步才能找到中位数。
那能不能一次跳过一大段，而不是一次只走一步？
当然是能。
举例
想象你在一本很厚的电话本里找张三这个名字。
笨方法:从第一页开始翻，一页一页翻，直到找到张三。
聪明的办法:先翻到中间，加入看到李四，因为李在张前面，所有张三肯定在后面半本。然后后面半本再翻到中间。
这就是二分查找的思想：每次排除一半的数据。
#### 分析
但是现在我们有两个排序数组，不是一个。
怎么对两个数组用二分查找？
我们不需要真的合并数组，我们只需要在逻辑上把它们分成左右两半。
想象以下，如果两个数组已经合并好了，从中间切一刀:
左半部分 右半部分
[小, 小, 小] | [大, 大, 大]
中位数就在这条切线的旁边。
问题转化为:我们能不能在不实际合并的情况下，找到这条切线在哪里？
答案是可以。
因为两个数组各自都是排序的，所以我们只需要决定:
- 从数组A中拿多少个元素放到左边
- 从数组B中拿多少个元素放到左边
我们只要保证以下两个条件就可以:
- 左边总数 = 右边总数 (奇数个的时候是相等，如果是偶数个的时候两边总数会差1)
- 左边最大的数 <= 右边最小的数
那么中位数就在切线旁边。
但是怎么找到这个切分点？
现在问题变成了：我们怎么知道A左边拿几个？B左边拿几个？
答案是：在短数组上二分查找。
因为一旦决定了A左边拿几个(记为i个)，那B左边拿几个就确定了，B左边拿的个数 = （总长度 + 1）/ 2 - i个，这里就把B左边拿几个的值记为j。
这个公式就保证了左边总数 = 右边总数 (或差1)
然后我们检查:
- 如果A[i - 1] <= B[j] 且 B[j - 1] <= A[i]， 那这就是中位数
- 如果A[i - 1] > B[j]，说明A左边拿的太多了，i需要减小
- 如果B[j - 1] > A[i]，说明A左边拿的太少了，i需要增大
这不就是二分查找吗？ 每次调整i，都能排除一半的可能性。
示例：用完整的例子跑一遍
A = [1, 3, 5, 7] 长度4
B = [2, 4, 6, 8] 长度4
总长度 = 8
- 第一次尝试
i = 2（A左边拿2个：1, 3）
j = (8+1)/2 - 2 = 4 - 2 = 2（B左边拿2个：2, 4）
左边：[1, 3, 2, 4] → 最大 = max(3, 4) = 4
右边：[5, 7, 6, 8] → 最小 = min(5, 6) = 5
4 ≤ 5 ✅ 完美！
中位数 = (4 + 5) / 2 = 4.5
为什么这个方法快?
因为我们在短数组上二分查找，每次排除一半的可能性。
如果短数组长度是m，我们只需要O(log m)次比较就能找到切分点。
而暴力合并需要O(m + n)次操作。
当m和n都是100万时:
- 暴力法:200万步
- 二分法:约20步
这道题的本质是：在两个排序数组中找中位数，等价于找一条虚拟的切线，把两个数组分成左右两半，使得左边全部小于右边。而找这条切线的最快方法，就是在较短的数组上做二分查找。
fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
// 确保 nums1 是较短的数组，这样二分更快
if (nums1.size > nums2.size) {
return findMedianSortedArrays(nums2, nums1)
}
val m = nums1.size
val n = nums2.size
var left = 0
var right = m
while (left <= right) {
// 在 nums1 中切 i 刀，左边有 i 个元素
val i = left + (right - left) / 2
// 在 nums2 中切 j 刀，保证左右两边元素数量平衡
val j = (m + n + 1) / 2 - i
// 四个关键元素
val nums1LeftMax = if (i == 0) Int.MIN_VALUE else nums1[i - 1]
val nums1RightMin = if (i == m) Int.MAX_VALUE else nums1[i]
val nums2LeftMax = if (j == 0) Int.MIN_VALUE else nums2[j - 1]
val nums2RightMin = if (j == n) Int.MAX_VALUE else nums2[j]
// 检查是否满足条件：左边最大 ≤ 右边最小
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 找到正确的切分点了！
return if ((m + n) % 2 == 0) {
// 偶数长度：取左边最大值和右边最小值的平均
(maxOf(nums1LeftMax, nums2LeftMax) + minOf(nums1RightMin, nums2RightMin)) / 2.0
} else {
// 奇数长度：取左边最大值
maxOf(nums1LeftMax, nums2LeftMax).toDouble()
}
} else if (nums1LeftMax > nums2RightMin) {
// nums1 左边太大了，需要往左移
right = i - 1
} else {
// nums1 左边太小了，需要往右移
left = i + 1
}
}
// 理论上不会到这里
return 0.0
}
举例:
nums1 = [1, 3, 5] (m=3)
nums2 = [2, 4, 6, 8] (n=4)
总长度 = 7（奇数），中位数应该是第4小的数
===== 第1轮 =====
left=0, right=3, i=1（nums1左边有1个元素）
j = (3+4+1)/2 - 1 = 4 - 1 = 3（nums2左边有3个元素）
左边：[1 | ...] + [2, 4, 6 | ...]
右边：[3, 5 | ...] + [8 | ...]
四个关键元素：
nums1LeftMax = nums1[0] = 1
nums1RightMin = nums1[1] = 3
nums2LeftMax = nums2[2] = 6
nums2RightMin = nums2[3] = 8
检查：1 ≤ 8 ✅，但 6 ≤ 3 ❌
→ nums2LeftMax(6) > nums1RightMin(3)
→ 需要让 nums1 更大一些，往右移 → left = 2
===== 第2轮 =====
left=2, right=3, i=2（nums1左边有2个元素）
j = 4 - 2 = 2（nums2左边有2个元素）
左边：[1, 3 | ...] + [2, 4 | ...]
右边：[5 | ...] + [6, 8 | ...]
四个关键元素：
nums1LeftMax = nums1[1] = 3
nums1RightMin = nums1[2] = 5
nums2LeftMax = nums2[1] = 4
nums2RightMin = nums2[2] = 6
检查：3 ≤ 6 ✅，4 ≤ 5 ✅ → 完美！
总长度为奇数，中位数 = max(3, 4) = 4
答案：4.0 ✅
Q：为什么要选较短的数组来二分？
A：时间复杂度是 O(log(min(m, n)))，选短的二分效率更高。如果选长的二分，log 值会更大。
Q：(m + n + 1) / 2 - i这个公式怎么来的？
A：我们要保证左右两边元素数量平衡：
总共有 m+n 个元素
左边应该有 (m+n+1)/2 个元素（向上取整，这样奇数时左边多一个）
左边来自 nums1 的有 i 个，所以来自 nums2 的就是 (m+n+1)/2 - i 个
Q：边界条件怎么处理？
A：用 Int.MIN_VALUE和 Int.MAX_VALUE来处理：
如果 i=0，说明 nums1 左边没元素，左边最大设为极小值
如果 i=m，说明 nums1 右边没元素，右边最小设为极大值
这样比较时就不会影响结果
复杂度
- 时间复杂度: O(log(min(m, n))) — 在较短的数组上二分
- 空间复杂度: O(1) — 只用了几个变量
- 邮箱 ：charon.chui@gmail.com
- Good Luck!