LeetCode-Go 题解：0004.Median of Two Sorted Arrays 二分切分求双有序数组中位数

LeetCode-Go 题解：0004.Median of Two Sorted Arrays 二分切分求双有序数组中位数

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本题（LeetCode 4. Median of Two Sorted Arrays）要求在两个已排序数组中找到合并后数组的中位数，且整体时间复杂度必须为 O(log(m+n))。本文以 LeetCode-Go 仓库中该题的中英文题解文档为骨架，结合 源码实现 与 单元测试 逐行拆解其核心思路：如何把「求中位数」转化为「在较短数组上二分切分位置」，以及奇数/偶数长度下如何取左中值与右中值。读完本文，你将掌握一套可迁移的二分切分（Binary Search on Partition）模板，理解其边界处理细节，并能直接运行仓库测试用例验证结论。

题目回顾

题目原文见 题解文档，核心约束如下：

• 给定两个大小分别为 m 和 n 的已排序数组nums1与nums2；
• 找出这两个数组合并后有序数组的中位数；
• 时间复杂度要求O(log(m+n))；
• 可以假设nums1与nums2不会同时为空。

示例一：

nums1 = [1, 3] nums2 = [2] 中位数 = 2.0

示例二：

nums1 = [1, 2] nums2 = [3, 4] 中位数 = (2 + 3) / 2 = 2.5

为什么不能直接合并：O(m+n) 不符合题意

最直观的想法是把两个数组合并成有序数组后直接取中位数。但合并两个有序数组本身是 O(m+n) 的操作，不满足题目要求的 O(log(m+n))。

看到对数级复杂度，自然联想到二分搜索。关键洞察在于：

• 两个数组的总长度m+n已知，因此中位数在最终合并数组中的位置也是确定的（第(m+n+1)/2个，1-based）；
• 只需要在一个数组上二分切分位置，另一个数组的切分位置即可由总数减出；
• 为了把时间复杂度降到最低，应当二分搜索两个数组中较短的那个（这是 O(log(min(m,n))) 的来源，也严格满足 O(log(m+n))）。

这一推理过程完整记录在 题解文档的 Solution Ideas 一节，仓库的 源码实现 第一步就体现了这一策略：若len(nums1) > len(nums2)，则交换两数组递归调用，保证nums1恒为较短者。

二分切分法：核心原理

1. 用一条切分线把两个数组切成左右两半

对较短数组nums1二分出一个切分点midA，则：

nums1: ……………… nums1[midA-1] | nums1[midA] …………………… nums2: ……………… nums2[midB-1] | nums2[midB] ……………………

其中竖线|即切分线：左侧包含nums1[0..midA-1]与nums2[0..midB-1]，右侧包含nums1[midA..]与nums2[midB..]。切分线两侧的元素数必须满足中位数的位置约束，即左右两侧元素个数相等（或左侧比右侧多一个）。

由于两个数组总长度已知，中间位置k = (len(nums1)+len(nums2)+1) >> 1（向上取整的一半，保证左侧元素数 ≥ 右侧），因此一旦确定了midA，midB = k - midA就被唯一确定。

2. 切分线满足中位数条件的判定

切分线何时是「合法」的？即线左边的所有数都小于等于线右边的所有数，形式化为：

nums1[midA-1] ≤ nums2[midB] && nums2[midB-1] ≤ nums1[midA]

若该条件不满足，则需要调整切分线位置，调整方向有两种：

• 若nums1[midA] < nums2[midB-1]：说明midA这条线划分出来的左侧元素整体偏小，切分线应当右移（low = midA + 1）；
• 若nums1[midA-1] > nums2[midB]：说明midA这条线划分出来的左侧元素整体偏大，切分线应当左移（high = midA - 1）。

经过若干次二分调整，总能找到满足条件的切分线。这正是二分搜索在有序数组上收敛性的体现：越界或不等价关系会在一次二分中把搜索区间缩小一半。

3. 找到切分线后如何取中位数

假设已找到合法切分线，数组 1切分线两侧下标为midA - 1与midA，数组 2切分线两侧下标为midB - 1与midB。

• 奇数总长度：中位数就是左侧的最大值，即max(nums1[midA-1], nums2[midB-1])；
• 偶数总长度：中间两个数依次为左侧最大值与右侧最小值，即max(nums1[midA-1], nums2[midB-1])和min(nums1[midA], nums2[midB])，中位数为二者平均值。

原文档在此处配有一张切分示意图片（原图存放于文档作者的外部图床，仓库内未收录，故本文以文字与代码注释复现同一示意图）。

源码逐行拆解

仓库中的 核心实现 完整代码如下：

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { // 假设 nums1 的长度小 if len(nums1) > len(nums2) { return findMedianSortedArrays(nums2, nums1) } low, high, k, nums1Mid, nums2Mid := 0, len(nums1), (len(nums1)+len(nums2)+1)>>1, 0, 0 for low <= high { // nums1: ……………… nums1[nums1Mid-1] | nums1[nums1Mid] …………………… // nums2: ……………… nums2[nums2Mid-1] | nums2[nums2Mid] …………………… nums1Mid = low + (high-low)>>1 // 分界限右侧是 mid，分界线左侧是 mid - 1 nums2Mid = k - nums1Mid if nums1Mid > 0 && nums1[nums1Mid-1] > nums2[nums2Mid] { // nums1 中的分界线划多了，要向左边移动 high = nums1Mid - 1 } else if nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid-1] { // nums1 中的分界线划少了，要向右边移动 low = nums1Mid + 1 } else { // 找到合适的划分了，需要输出最终结果了 // 分为奇数偶数 2 种情况 break } } midLeft, midRight := 0, 0 if nums1Mid == 0 { midLeft = nums2[nums2Mid-1] } else if nums2Mid == 0 { midLeft = nums1[nums1Mid-1] } else { midLeft = max(nums1[nums1Mid-1], nums2[nums2Mid-1]) } if (len(nums1)+len(nums2))&1 == 1 { return float64(midLeft) } if nums1Mid == len(nums1) { midRight = nums2[nums2Mid] } else if nums2Mid == len(nums2) { midRight = nums1[nums1Mid] } else { midRight = min(nums1[nums1Mid], nums2[nums2Mid]) } return float64(midLeft+midRight) / 2 }

关键变量与二分框架

注意nums1Mid = low + (high-low)>>1的写法：先算差值再右移一位，等效于(low+high)/2，但可避免整型溢出，是二分模板中的推荐写法。

边界条件的四个分支

midLeft的取值需要处理切分线落在数组边缘的情况：

1. nums1Mid == 0：nums1整体都在切分线右侧，左侧最大值只能来自nums2，取nums2[nums2Mid-1]；
2. nums2Mid == 0：nums2整体都在切分线右侧，左侧最大值只能来自nums1，取nums1[nums1Mid-1]；
3. 其余情况：左侧最大值取max(nums1[nums1Mid-1], nums2[nums2Mid-1])。

midRight同理有对称的三个分支（nums1Mid == len(nums1)、nums2Mid == len(nums2)、一般情况取min(...)）。这四个边界分支是本题最容易写错的地方，也正是 单元测试 中用专门用例逐一覆盖的原因（详见下文）。

奇偶长度的收尾

• 总长度为奇数时：(m+n)&1 == 1，直接返回float64(midLeft)，即左侧最大值即为中位数；
• 总长度为偶数时：返回float64(midLeft+midRight)/2，即左右两个中间值的平均数。

单元测试如何验证每个分支

仓库为该题编写了 9 组用例，存放在 4. Median of Two Sorted Arrays_test.go，每组用例都有明确的覆盖意图：

测试框架采用表驱动风格：para4封装两个输入数组，ans4封装期望答案，测试循环对每组(para, ans)调用findMedianSortedArrays，一旦结果与期望不符即t.Fatalf失败并打印输入与输出。从测试注释可以看出，作者刻意覆盖了「短数组在前 / 长数组在前」「切分线落在数组两端」「元素全部相等」等极端场景，为二分边界正确性提供了可复现的验证依据。

如需在本地运行该测试，可执行：

go test -v ./leetcode/0004.Median-of-Two-Sorted-Arrays/

若想生成并查看全仓库覆盖率报告，仓库根目录的 gotest.sh 提供了标准做法：

bash gotest.sh go tool cover -func=coverage.txt | grep findMedianSortedArrays

复杂度分析

• 时间复杂度：二分搜索仅在较短数组上进行，每次迭代将搜索区间减半，因此为 O(log(min(m,n)))；又因为 min(m,n) ≤ (m+n)/2，log(min(m,n)) ≤ log(m+n)，严格满足题目要求的 O(log(m+n))；
• 空间复杂度：除常数个变量（low、high、k、nums1Mid、nums2Mid、midLeft、midRight）外无额外分配，为 O(1)；递归 swap 仅发生在首层，深度为 1，不随输入规模增长。

总结

本题的标准解法是把「合并求中位数」转化为「在较短有序数组上二分切分位置」，用k反推另一数组的切分位置，通过两条不等式判定切分线合法性并二分调整，最后按奇偶长度取左侧最大值（与右侧最小值）计算中位数。仓库的 源码实现 结构清晰、边界完备，题解文档 给出了从 O(m+n) 朴素思路到 O(log(min(m,n))) 二分方案的完整推导路径，单元测试 则为每个边界分支提供了可运行验证。掌握「短数组二分 + 位置反推 + 奇偶收尾」这一模板后，可以平滑迁移到其他「有序结构中求第 k 小」类问题。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go