两个正序数组找中位数：二分排除法与划分数组法详解

我一开始接触这道题的时候，觉得它就是个简单的“归并排序取中间值”问题，不就是把两个数组合并起来，然后按下标取值吗？直到我读到题目里那个O(log(m+n))的时间复杂度要求，才意识到事情没那么简单。这道题是数组二分操作里非常经典的一道，也是常被拿来考“你是不是真懂二分搜索”的试金石。无论你是在准备算法面试，还是日常写业务代码时遇到“两份有序数据求整体分位点”的需求，这套思路都用得上。

所谓“寻找两个正序数组的中位数”，说白了就是给定两个从小到大排好的数组，把两者看成一个整体后，找出这个整体序列中间位置的数值。看起来朴素，但难点全在那句“对数级时间复杂度”上。这篇我会把两种主流解法都拆开讲透：一种是“第 K 小元素”的排除法，一种是“划分数组”切割法，并附上完整的实现代码、边界处理说明和一份避坑清单。

1. 题目拆解：标题里藏着的三个关键词

1.1 “正序数组”意味着什么

先聊“正序”。这俩字是整个题目的信息红利所在。如果一个数组是无序的，你找中位数最快也得先排序，O(n log n)起步。但只要数组有序，你就可以用二分查找、双指针这类“利用位置信息”的手段，把搜索范围成半点地缩小。

这也是我在实际工作中非常依赖的直觉：有序数据是无价的。无论是数据库索引、日志时间序列，还是接口返回的已排序列表，遇到这类数据，第一步不是遍历，而是先想想“能不能二分”。本题目里的两个正序数组，就是给你两块积木，让你通过位置比较来快速收敛答案。

1.2 “中位数”的本质是第 K 小的数

很多同学一上来就纠结奇偶性，其实完全没必要。中位数的定义可以统一成一句话：在长度为total的有序序列里，中位数是第total/2 + 1个元素（奇数情况），或者第total/2和第total/2 + 1个元素的平均值（偶数情况）。

所以这道题本质上可以转化为一个更通用的子问题：两个正序数组中，如何找第 K 小的数。一旦你写出了getKth函数，中位数不过就是调用它两次取平均而已。

总长度 total = m + n 若 total 为奇数：中位数 = 第 (total/2 + 1) 小的数 若 total 为偶数：中位数 = (第 total/2 小的数 + 第 (total/2 + 1) 小的数) / 2

举个例子，nums1 = [1, 3]，nums2 = [2]，total = 3。我们需要第3/2 + 1 = 2小的数，合并后是[1, 2, 3]，第2小是2，中位数就是2。而nums1 = [1, 2]，nums2 = [3, 4]，total = 4，需要第2小和第3小的平均数，也就是2和3的平均值2.5。

1.3 为什么复杂度要求是 O(log(m+n))

如果允许O(m+n)，代码五分钟就能写完：双指针归并，走到中间两格取平均。但题目要求的O(log(m+n))直接把这条路堵死了。这个复杂度恰恰暴露了出题人的真实意图：它不满足于“你会写循环”，它想考的是“你懂不懂排除一半”。

log(m+n)级别的算法，每轮操作必须能丢掉大约一半的候选元素。这就逼着你想：能不能像二分查找那样，每次比较两个数组中的某个位置，然后一次性排除掉不可能包含答案的那一片区域？答案是肯定的。这也是整道题最核心的思维跳跃点。

2. 解法一：二分排除法，每次丢掉一半

2.1 先把问题转化成“找第 K 小的数”

二分排除法（也叫“第K小排除法”）的思路非常直白：既然要在两个有序数组中找第K小的数，那我每次就设法排除掉K/2个候选元素，让K不断减小。当 K 缩小到 1 时，问题就变得极其简单：两个数组剩余部分的最小值，就是答案。

我可以用一个例子把流程走一遍。假设：

nums1 = [1, 3, 5, 7, 9] nums2 = [2, 4, 6, 8, 10] K = 5

第一轮，K/2 = 2。比较nums1的第2个元素3，和nums2的第2个元素4。因为3 < 4，那么nums1的前2个元素（1, 3）绝对不可能是全局第5小的元素——原因是比它们小的元素最多只有nums1里的1个和nums2里的1个，合计最多3个。所以这2个元素可以直接丢掉。K 变成5 - 2 = 3。

第二轮，两个数组的剩余部分分别是nums1 = [5, 7, 9]和nums2 = [2, 4, 6, 8, 10]。K/2 = 1。比较第1个元素：5和2。2 < 5，丢掉nums2的第1个元素2。K 变成2。

第三轮，剩余部分是nums1 = [5, 7, 9]，nums2 = [4, 6, 8, 10]。K/2 = 1。比较5和4，4 < 5，丢掉4。K 变成1。

此时K等于1，直接返回两个数组剩余的最小值，即min(5, 6) = 5。我们验证一下：两个数组合并后是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，第5小的数确实是5。

2.2 为什么比较 K/2 位置是合理的

你可能会问：为什么选K/2，而不是选K/3或者别的？核心原因是：想要在 O(logK) 内完成，每轮都要把 K 减少固定的比例，而选 K/2 是最自然、最好写的比例。

细想一层：如果nums1[K/2 - 1] < nums2[K/2 - 1]，说明nums1的前 K/2 个元素中，任意一个元素x，在另一个数组里能找到多少个比x小的元素？最坏情况下，nums2的前 K/2 - 1 个元素也可能全部小于x，加上nums1自身排在x前面的那些元素，比x小的元素总数最多也就是(K/2 - 1) + (K/2 - 1) = K - 2个，仍然小于 K-1。换句话说，这 K/2 个元素里不可能有全局第K小，排除它们没有任何风险。

这个“排除一定不可能是答案的元素”的手法，和二分查找里“砍掉不可能区间”的本质一模一样。

2.3 完整实现与边界设计

下面给出我常用的Java版本，用了两个索引i和j分别指向两个数组的剩余起点，没有实际拷贝数组，空间开销只是 O(1)。

public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total = nums1.length + nums2.length; if (total % 2 == 1) { return getKth(nums1, nums2, total / 2 + 1); } else { return (getKth(nums1, nums2, total / 2) + getKth(nums1, nums2, total / 2 + 1)) / 2.0; } } private int getKth(int[] nums1, int[] nums2, int k) { int m = nums1.length, n = nums2.length; int i = 0, j = 0; while (true) { if (i == m) { return nums2[j + k - 1]; } if (j == n) { return nums1[i + k - 1]; } if (k == 1) { return Math.min(nums1[i], nums2[j]); } int half = k / 2; int newI = Math.min(i + half, m) - 1; int newJ = Math.min(j + half, n) - 1; if (nums1[newI] <= nums2[newJ]) { k -= (newI - i + 1); i = newI + 1; } else { k -= (newJ - j + 1); j = newJ + 1; } } }

我重点说说几处边界：

• newI和newJ为什么要用Math.min(i + half, m) - 1？因为k/2可能比数组剩余长度还大。比如nums1只剩 1 个元素，但k = 5，那i + half就会越界。取min的意思是：我最多只能排除这个数组剩余的全部元素，不能超出数组边界。

• 排除元素数量用newI - i + 1，而不是直接用half。因为上面做了截断，实际排除的可能比half少。比如一个数组本身只剩 3 个元素，half = 4，你只能排除 3 个。

• 当k == 1时，直接返回两个数组当前头部较小的那个。这也是递归/循环的终止条件。

2.4 时间复杂度的直观证明

每轮循环，K 至少减半。K 的初始值是(m+n)/2级别，最坏情况下经过 O(log(m+n)) 轮，K 会降到 1。每轮只有常数次比较，所以整体时间复杂度是 O(log(m+n))，空间复杂度 O(1)。

我实际测试过这个方法在极端情况下的表现，比如nums1为空、nums2长度为百万级别，它也能在几十次比较内出结果，远快于归并。

3. 解法二：划分数组法，从切割的视角理解

3.1 核心思想：在两个数组里各自切一刀

二分排除法的逻辑很“动态”，每轮都在排除。另一种更符合“中位数定义”的思路是：把两个数组分别切成左右两段，使得左半部分的元素总数刚好等于右半部分（或比右半部分多一个），而且左半部分的最大值不大于右半部分的最小值。

假设在nums1的第i个元素后面切一刀，在nums2的第j个元素后面切一刀，那么：

nums1 左半部分：nums1[0 .. i-1] nums1 右半部分：nums1[i .. m-1] nums2 左半部分：nums2[0 .. j-1] nums2 右半部分：nums2[j .. n-1]

只要满足两个条件：

1. i + j = (m + n + 1) / 2，保证左半部分元素数不少于右半部分；
2. nums1[i-1] <= nums2[j]且nums2[j-1] <= nums1[i]，保证左半部分所有元素都不大于右半部分所有元素。

那么中位数就很好求了：如果总长度是奇数，一定是左半部分最大值；如果是偶数，是左半部分最大值和右半部分最小值的平均值。

我用生活例子解释一下：想象两副牌，每副都按从小到大排列。我现在要拼出一副完整的升序大牌堆，从中间把大牌堆分成两堆。只要我知道大牌堆中间左边最大的是什么、右边最小的是什么，中位数就有了。而“切”的过程，就是去找那个能让两边大小关系正确的分割点。

3.2 为什么(m + n + 1) / 2是个好公式

无论总长度奇偶，我都希望左半部分比右半部分多一个元素或一样多。设totalLeft = (m + n + 1) / 2，对于整数除法：

• total = 5，totalLeft = 3，左3右2，左多一个；
• total = 6，totalLeft = 3，左3右3，左右相等。

也就是说，奇数时左半部分多出来的那一个元素，就是中位数；偶数时中位数是左边最大值和右边最小值的平均。这个公式把奇偶情况统一起来了。

在代码中，我们只在较短的数组nums1上二分搜索i，然后通过j = totalLeft - i自动算出第二个数组的切割位置。i的范围是[0, m]，二分后自然得到唯一的合理分割。

3.3 完整代码与三个边界保护

public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证 nums1 是较短的那个数组，缩短二分查找的范围 if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.length, n = nums2.length; int totalLeft = (m + n + 1) / 2; int left = 0, right = m; while (left <= right) { int i = (left + right) / 2; int j = totalLeft - i; if (i > 0 && j < n && nums1[i - 1] > nums2[j]) { // 说明 i 切得太靠右，a 的左半边最大元素大于 b 的右半边第一个元素 right = i - 1; } else if (j > 0 && i < m && nums2[j - 1] > nums1[i]) { // 说明 i 切得太靠左，b 的左半边最大元素大于 a 的右半边第一个元素 left = i + 1; } else { // 找到了满足条件的分割点 int aLeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; int aRightMin = (i == m) ? Integer.MAX_VALUE : nums1[i]; int bLeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; int bRightMin = (j == n) ? Integer.MAX_VALUE : nums2[j]; if ((m + n) % 2 == 1) { return Math.max(aLeftMax, bLeftMax); } else { return (Math.max(aLeftMax, bLeftMax) + Math.min(aRightMin, bRightMin)) / 2.0; } } } return 0.0; }

这里的边界保护非常关键，我逐个说明：

• 当i == 0时，nums1左半部分是空的，aLeftMax应该视为Integer.MIN_VALUE，相当于“负无穷”，不会干扰Math.max的结果。
• 当i == m时，nums1右半部分是空的，aRightMin应该视为Integer.MAX_VALUE，相当于“正无穷”，不会干扰Math.min的结果。
• 二分条件里j < n和i < m是为了防止访问不存在的数组位置。例如j可能等于n，此时nums2[j]越界，需要短路退出。

3.4 为什么要强制“对较短的数组二分”

有两方面考虑。

一是时间复杂度。i的范围是[0, m]，二分的复杂度是 O(log m)，所以m越小越快。如果nums1有 1000 个元素、nums2有 100 万个，对 1000 那个做二分，代价只有 10 次左右。

二是正确性。j = totalLeft - i必须落在[0, n]范围内。如果我在更长的数组上二分，短数组的j = totalLeft - i可能变成负数或超过n，公式就不成立了。先交换，确保m <= n，j的边界才自动安全。

4. 两种解法对比与“有序数据处理”的延伸

4.1 一张表看懂两种解法的差异

我个人倾向在面试中先说“二分排除法”，因为它的推导过程更直观，不容易卡壳。等面试官追问“能不能再优化”时，再补上划分数组法。两种方法不是对立关系，后者本质上是前者的变体，只是从“排除”变成了“划分”。

4.2 如果题目变成链表版本，思路要转变

标题里写着“数组/链表操作”，很多同学会问：nums1和nums2如果是链表呢？

链表的麻烦在于无法 O(1) 随机访问，二分法的根基没了。找两个有序链表的中位数，常规做法是归并，复杂度 O(m+n)。如果是单个链表找中点，则可以用快慢指针：快指针每次走两步，慢指针每次走一步，快指针到末尾时，慢指针正好在中点。

这个对比很有意义。它提醒我们：所谓“算法”，不只是记住模板，而是要针对数据结构的特点选择操作方式。数组支持随机访问，二分才成立；链表只能顺序访问，快慢指针才是它的主场。

顺带一提，热词里那些“链表遍历、链表插入、单链表逆序”的操作，本质上都是对链表“只能逐节点访问”这个特性的应对。理解了这一点，再看本题目里的数组二分，你的知识结构才算真正串起来。

4.3 这道题可以迁移到哪些实际场景

“两个正序数组找中位数”不是一道孤立的面试题。我列几个实际场景，你就知道它的价值了：

• 日志系统分位点统计：假设你有两份按时间排序的日志，需要计算整体耗时的 P50、P90。如果数据量太大不能合并，就得分治定位。
• 数据库查询优化：针对多个有序索引段求全局中间位置的记录，类似这里的二分排除。
• 数据流中的中位数：如果数据源源不断进来，就不能用这道题的双数组模型，而要改用两个堆（大顶堆+小顶堆）维护。这道题是理解“静态有序集合中求中位数”的基础，数据流版本是它的动态扩展。

所以别把刷题当背题。每道题背后都是一个可迁移的套路：有序 → 尝试二分；中位数 → 尝试转化为第K小；第K小 → 每次排除一半。

5. 常见问题与避坑清单

5.1 边界条件速查表

我整理了一份问题排查对照表，这些都是我写代码时真实踩过的坑：

5.2 我实际调试中的几条经验

写这道题，我建议你完完整整地把两个版本的代码都手写一遍，然后跑这一组测试用例：

[1,3] 和 [2] → 2.0 [1,2] 和 [3,4] → 2.5 [] 和 [1] → 1.0 [1] 和 [] → 1.0 [1,1] 和 [1,1] → 1.0 [1,3,5,7,9] 和 [2,4,6,8,10] → 5.5

这组用例里的[]空数组、全相等数组、奇偶长度组合，几乎能覆盖所有边界情况。

我自己的调试体会是：不要一上来就调边界，先在纸上模拟一轮“K=5”的完整流程，把每次排除的元素和 K 的变化写下来。只要你亲手走通一个例子，代码里newI和newJ的设计逻辑就清楚了。反之，直接对着代码改下标，越改越乱。

5.3 面试中容易被追问的几个点

面试官不会只满足于“你会写”，他大概率会顺着往下问：

• “如果其中一个数组特别小，另一个特别大，有什么影响？”——这正是为什么要对短数组二分的动机。
• “能不能把这个方法推广到求第 K 小的数？”——完全可以，getKth本身就是通用函数。
• “如果两个数组长度加起来是偶数，中位数为什么取平均？”——回到定义。
• “为什么nums1[i-1] <= nums2[j]时不用再比较nums2[j-1] <= nums1[i]？”——因为二分过程中两边互相牵制，i移动后另一侧自然满足，理解这一点能避免写重复判断。

我在面试别人时，最怕听到候选人背代码。你只要能把O(log(m+n))为什么成立讲清楚，比默写十遍代码都有用。

6. 最后分享一点我的个人习惯

关于这道题，我想以实际经验收尾。我最初学这道题时，总想着把两种解法的代码都背下来，结果没过多久就忘光了。后来我换了一种方式：把“第 K 小排除法”当成一种套路来记，把“每个数组成员都取 K/2 位置做比较”这个画面刻在脑子里，遇到任何有序数组相关的题目，都能自然套用。

朋友跟我讨论算法时经常说，最难的不是写对，而是“想不到”。我觉得，像“两个有序数组找中位数”这种题，核心就是给你一个思维范式：有序集合里找特定位置的数，优先想二分，每次排除一半。一旦你把这个范式内化了，它就不只是一道题的答案，而是一种解决问题的底层的思维习惯。

我自己在之后处理生产环境的日志分位点统计时，就参考了这个思路。数据按时间分片存储，每个分片内部有序，求全局 P95 时，我用类似排除法的方式逐步缩小候选区间，把原来几分钟的全量聚合降到了秒级。所以说，这道题刷的值不值，不在于你背了多少行代码，而在于你有没有真正理解“为什么可以一次次排除一半”。理解了这一层，它给你带来的收益将远超中位数本身。