LeetCode 0004《寻找两个正序数组的中位数》：基于二分查找的 O(log(m+n)) 解法详解（AlgoNote 算法通关手册）

• 教程
• 文档
• 知识库

导读

本篇技术指南围绕「算法通关手册（AlgoNote）」中 LeetCode 0004《寻找两个正序数组的中位数》题解 展开，深入讲解如何在两个有序数组中利用**二分查找（Binary Search）与分治（Divide and Conquer）**思想，以 $O(\log(m+n))$ 的时间复杂度定位中位数。读完本文，你将掌握「第 k 小元素」二分查找法的推导逻辑、边界条件处理技巧，以及仓库源码中归并排序、二分查找基础算法与本解法之间的关联，可直接复刻该解法应对同类面试题。

一、题目概述与约束

题目：给定两个正序（从小到大排序）数组nums1、nums2，找出并返回这两个正序数组的中位数。

• 标签：数组、二分查找、分治
• 难度：困难

约束条件（来自 原题解文档）：

• 算法的时间复杂度应该为 $O(\log(m + n))$。
• nums1.length == m。
• nums2.length == n。
• $0 \le m \le 1000$。
• $0 \le n \le 1000$。
• $1 \le m + n \le 2000$。
• $-10^6 \le nums1[i], nums2[i] \le 10^6$。

示例 1：

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 2：

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

值得注意：由于题目要求 $O(\log(m+n))$，而 $m, n \le 1000$、$m + n \le 2000$，直接归并两个数组后取中位数的做法虽然正确，但时间复杂度为 $O(m+n)$，无法满足题目对时间复杂度的硬性要求。这正是本题被标记为「困难」的核心原因——必须利用有序数组的二分性质，将查找规模压缩到对数级别。

二、解题思路：从归并到二分查找

2.1 朴素思路：归并拼接

单个有序数组的中位数就是中间位置元素（若中间位置对应两个元素，则取二者平均数）。如果是两个有序数组，一个最直观的办法是用归并的方式拼接成一个大数组：

• 归并排序中的merge过程（仓库源码 codes/python/01_array/array_sort_merge_sort.py）正是「两个有序子数组合并」的典型实现：双指针依次取出较小元素，直到一方耗尽再追加剩余元素；
• 合并后的大数组长度为 $(n1 + n2)$，其中间位置的元素即为中位数。

但正如上文所述，归并需要线性时间，并不满足 $O(\log(m+n))$ 的要求。因此我们需要跳脱「真正合并出完整数组」的思路——只需找到中位数的位置即可。

2.2 关键观察：中位数把数组切成左右两半

设 $n1$、$n2$ 分别为nums1、nums2的长度，合并后的总长度为 $(n1 + n2)$。观察中位数的定义可以发现一个核心性质：

中位数把（合并后的）数组分割成了左右两部分，并且左右两部分元素个数相等。

由此可以分奇偶两种情况讨论：

• 若 $(n1 + n2)$ 是奇数，中位数是合并后数组中第 $\lfloor \frac{(n1 + n2)}{2} \rfloor + 1$ 个元素，包含中位数在内的单侧元素个数为 $\lfloor \frac{(n1 + n2)}{2} \rfloor + 1$；
• 若 $(n1 + n2)$ 是偶数，中位数是第 $\lfloor \frac{(n1 + n2)}{2} \rfloor$ 与第 $\lfloor \frac{(n1 + n2)}{2} \rfloor + 1$ 两个元素的平均值，单侧元素个数为 $\lfloor \frac{(n1 + n2)}{2} \rfloor$。

由于是向下取整，两种情况下单侧元素个数可以统一写成：

$$ k = \left\lfloor \frac{n1 + n2 + 1}{2} \right\rfloor $$

于是原问题被等价转化为一个经典子问题：如何在两个有序数组中找出前 k 小的元素位置？

2.3 问题转化：枚举 m1 确定 m2

如果从nums1中取出前 $m1 \ (m1 \le k)$ 个元素，那么从nums2中就需要取出前 $m2 = k - m1$ 个元素。一旦在nums1中确定了合适的 $m1$，$m2$ 也随之唯一确定。

于是问题进一步收敛为：如何从nums1中选取前 $m1$ 个元素，使得分割线左半边恰好包含 k 个元素（即nums1的第 $m1$ 个元素或nums2的第 $m2 = k - m1$ 个元素位于中位线位置）。

这个「在有序区间中寻找满足条件的分割点」的过程，正是二分查找的用武之地。仓库中的二分查找基础文档 docs/01_array/01_13_array_binary_search_01.md 指出，二分查找的核心是「每次将查找区间缩小一半」；而 docs/01_array/01_14_array_binary_search_02.md 中的**「排除法」思想**——每轮循环优先排除掉一定不包含目标元素的区间，仅在可能存在目标的区间内继续查找——正是本题二分查找循环体的设计依据。

三、二分查找的实现细节

3.1 算法步骤

1. 初始化：令left指向nums1的头部位置0，right指向nums1的尾部位置n1；
2. 每轮取中间位置作为 $m1$，则 $m2 = k - m1$。然后比较nums1[m1]与nums2[m2 - 1]：
   • 若nums1[m1] < nums2[m2 - 1]，说明nums1中取的元素不够多（nums1[m1]不可能是第 k 个元素），应右移 $m1$，即left = m1 + 1；
   • 若nums1[m1] >= nums2[m2 - 1]，说明 $m1$ 取值可能偏大，按排除法思路收缩右边界，即right = m1；
3. 循环结束后，$m1$ 即为最终分割位置，$m2 = k - m1$；
4. 根据 $(n1 + n2)$ 的奇偶性与边界条件计算中位数。

3.2 为什么判断nums1[m1]与nums2[m2 - 1]的关系？

这是整个解法的核心推理点，推导如下：

若nums1[m1] < nums2[m2 - 1]，则：

1. nums1[m1]左侧比它小的元素共有 $m1$ 个（即nums1[0] ... nums1[m1 - 1]）；
2. nums2数组中最多有 $m2 - 1$ 个元素比nums1[m1]小（即便nums2[m2 - 1]左侧所有元素都比nums1[m1]小，也只有 $m2 - 1$ 个）；
3. 综合来看，nums1、nums2中最多有 $m1 + m2 - 1 = k - 1$ 个元素比nums1[m1]小；
4. 因此nums1[m1]左侧的 $m1$ 个元素（nums1[0] ... nums1[m1 - 1]）都不可能是第 k 个元素，可以全部排除，然后将 $m1$ 右移。

这个「排除不可能区间」的过程，与 docs/01_array/01_14_array_binary_search_02.md 中排除法的写法完全一致：当nums[mid] < target时排除[left, mid]区间、继续在[mid + 1, right]查找；反之收缩右边界为right = mid。本题将「目标值」替换成了「满足分割条件的 m1」，本质是同一套减治逻辑。

3.3 为何选择较短的数组进行二分？

在代码实现中有一行关键预处理：

if n1 > n2: return self.findMedianSortedArrays(nums2, nums1)

交换两个数组，保证始终在较短的nums1上做二分。这样做有两个好处：

• 二分区间[0, n1]更短，迭代次数更少；
• 更关键的是保证 $m2 = k - m1$ 恒为非负且不超过 $n2$。由于 $m1 \le n1$、$k = \lfloor (n1+n2+1)/2 \rfloor \ge n1$，可得 $m2 = k - m1 \ge k - n1 \ge 0$，且 $m2 \le k \le n2$，从而nums2[m2 - 1]、nums2[m2]的访问始终安全，避免越界。

3.4 参考代码

以下完整实现继承自 原题解文档 的「思路 1：代码」：

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n1 = len(nums1) n2 = len(nums2) if n1 > n2: return self.findMedianSortedArrays(nums2, nums1) k = (n1 + n2 + 1) // 2 left = 0 right = n1 while left < right: m1 = left + (right - left) // 2 # 在 nums1 中取前 m1 个元素 m2 = k - m1 # 在 nums2 中取前 m2 个元素 if nums1[m1] < nums2[m2 - 1]: # 说明 nums1 中所取元素不够多， left = m1 + 1 # 应右移 m1，排除左侧不可能区间 else: right = m1 # m1 可能偏大，收缩右边界 m1 = left m2 = k - m1 c1 = max(float('-inf') if m1 <= 0 else nums1[m1 - 1], float('-inf') if m2 <= 0 else nums2[m2 - 1]) if (n1 + n2) % 2 == 1: return c1 c2 = min(float('inf') if m1 >= n1 else nums1[m1], float('inf') if m2 >= n2 else nums2[m2]) return (c1 + c2) / 2

代码要点逐行拆解：

• k = (n1 + n2 + 1) // 2：统一奇偶两种情况的单侧元素个数；
• m1 = left + (right - left) // 2：用「left + (right - left) // 2」而非(left + right) // 2计算中间位置，避免加法溢出（这也是 docs/01_array/01_13_array_binary_search_01.md 中推荐的防溢出写法）；
• 二分结束后m1 = left：此时left == right，m1即为nums1中应取出的元素个数；
• c1：左半区间的最大值（即中位线左侧最后一个元素），取nums1[m1-1]与nums2[m2-1]的较大者；当m1 <= 0或m2 <= 0时用float('-inf')兜底；
• 若总长度为奇数，左半区间的最大值c1就是中位数，直接返回；
• 若总长度为偶数，还需右半区间的最小值c2（取nums1[m1]与nums2[m2]的较小者，越界时用float('inf')兜底），中位数即为(c1 + c2) / 2。

边界条件的必要性：float('-inf')与float('inf')的引入，正是为了覆盖m1 == 0、m2 == 0、m1 == n1、m2 == n2这四类极端情形（例如某个数组为空、或某个数组的元素全部被取走），保证nums1[m1 - 1]、nums2[m2]等下标不会越界。

四、复杂度分析与分治思想印证

4.1 复杂度分析

• 时间复杂度：$O(\log(m + n))$。每轮循环将nums1上的查找区间缩小一半，而nums1是两数组中较短的一个（$n1 \le (m+n)/2$），二分迭代次数为 $O(\log n1) = O(\log(m+n))$；每次循环仅做常数次比较与赋值，因此总复杂度为 $O(\log(m+n))$，严格满足题目要求。
• 空间复杂度：$O(1)$。全程仅使用left、right、m1、m2、c1、c2等常数个变量，未申请与输入规模相关的额外空间（递归交换调用仅在第一次发生，不随规模增长）。

4.2 与仓库「分治算法」主题的呼应

本题在题目分类中被标记为「数组、二分查找、分治」（见 docs/00_preface/00_06_categories_list.md 的二分查找题目列表）。对照仓库 docs/07_algorithm/07_03_divide_and_conquer_algorithm.md 中的分治定义：

• 分解：把「找中位数」分解为「在两个有序数组中找前 k 小元素」，再进一步分解为「确定 m1、m2 两个分割点」；
• 求解：利用二分查找的排除法在nums1上对数级地逼近正确的 m1；
• 合并：根据奇偶性与边界条件，将左右两个分割边界元素c1、c2合并为中位数答案。

同时，本题朴素做法中「归并两个有序数组」的过程，在仓库源码 codes/python/01_array/array_sort_merge_sort.py 中有可直接对照的merge双指针实现。理解这两个维度——「线性归并」与「对数级二分」——的差异，正是吃透本题的关键。

五、总结与同类题目延伸

5.1 核心要点回顾

1. 中位数的分割性质：中位数把合并数组切分成元素个数相等的左右两部分，据此得到统一公式 $k = \lfloor (n1+n2+1)/2 \rfloor$；
2. 枚举 m1 确定 m2：在较短数组nums1上二分搜索 m1，m2 由 $m2 = k - m1$ 唯一确定；
3. 排除法二分：通过比较nums1[m1]与nums2[m2 - 1]排除不可能区间，循环条件left < right，终态left == right即为答案位置；
4. 边界兜底：用float('-inf')/float('inf')处理空侧与越界情形；
5. 复杂度达标：$O(\log(m+n))$ 时间、$O(1)$ 空间，是本题区分「合格解」与「暴力归并解」的分水岭。

5.2 同类题目延伸

二分查找（尤其是排除法写法）在本仓库题目体系中是高频考点，可继续延伸阅读：

• 基础二分查找：0704. 二分查找
• 二分边界类：0034. 在排序数组中查找元素的第一个和最后一个位置（排除法找边界的典型应用）
• 旋转数组二分：0033. 搜索旋转排序数组、0153. 寻找旋转排序数组中的最小值
• 二维有序结构二分：0074. 搜索二维矩阵、0240. 搜索二维矩阵 II
• 完整的二分查找题目列表见 docs/00_preface/00_06_categories_list.md。

掌握本题的「第 k 小元素二分法」后，再遇到任意变体（如n个有序数组求中位数、数据流中位数）时，都能快速迁移这套分割与排除的思想。

• 教程
• 文档
• 知识库