力扣第4题：双数组二分查找法高效求解中位数

1. 问题重述与核心难点剖析今天我们来啃一块硬骨头「力扣」第 4 题——寻找两个正序数组的中位数。这道题被标记为“困难”常年盘踞在各大算法面试的高频榜单上。很多朋友第一次看到题目描述可能会觉得“不就是找中位数吗把两个数组合并排序然后取中间那个或两个的平均不就行了” 这个思路完全正确并且是解决这个问题的“定义法”。如果面试中你能快速写出这个解法至少说明你的基础编码能力是过关的。但问题就出在题目给出的进阶要求上算法的时间复杂度应该为 O(log (mn))。这个 O(log (mn)) 就像一个紧箍咒直接把我们“合并后排序”的 O((mn)log(mn)) 想法给否定了也否定了使用双指针归并的 O(mn) 解法。它明确指向了我们必须使用对数级别的算法。在有序数组的语境下“对数”几乎就是“二分查找”的代名词。所以这道题的本质是要求我们在两个已排序的数组上不进行实际合并而是通过某种“划分”和“比较”的策略直接定位到合并后数组的中位数位置。这为什么难难点在于我们需要同时处理两个数组并且要保证划分后左半部分的所有元素都小于等于右半部分的所有元素同时左右两部分的元素数量还要相等或左半部分多一个。这个“划分”不是在一个数组上进行的而是在两个数组上协同进行的。你需要像玩一个高难度的平衡游戏同时调整两个数组上的“切割点”直到满足所有苛刻的条件。这需要你对二分查找的思想有非常深刻的理解并能够将其灵活应用到两个数组的协同搜索场景中。2. 从基础解法到进阶要求的思维跃迁在深入那个著名的 O(log(min(m, n))) 解法之前我们有必要先理解问题的基础形态和进阶要求之间的鸿沟这能帮助我们更好地欣赏高效解法的精妙之处。2.1 直观解法合并后查找假设我们有两个正序数组nums1和nums2长度分别为m和n。最直接的思路是创建一个新数组merged用双指针法按序合并两个数组这个过程时间复杂度是 O(mn)。合并后中位数就很简单了如果(mn)是奇数中位数是merged[(mn)//2]。如果(mn)是偶数中位数是(merged[(mn)//2 - 1] merged[(mn)//2]) / 2.0。这个方法的代码写起来很快也容易理解。在力扣上提交对于常规的测试用例也能通过。但它显然不满足 O(log(mn)) 的要求。面试官如果追问“有没有更优的解法” 而你只能停留在此那么这道题的得分可能就不太理想了。2.2 优化思路双指针归并不真正合并我们甚至可以再优化一步既然我们只关心中位数那是不是可以不用完全合并整个数组我们可以用两个指针i和j分别指向两个数组的开头然后模拟归并过程每次移动指向较小元素的指针并计数。当我们移动到第(mn)//2个或第(mn)//2和(mn)//2 - 1个元素时就找到了中位数。这个方法的时间复杂度是 O(mn)空间复杂度是 O(1)因为我们只用了几个指针变量。这比第一种方法在空间上更优但时间复杂度仍然没有达到对数级别。它像一个线性的扫描当数组非常庞大时效率依然不够高。然而这个“模拟归并计数”的思想非常重要它帮助我们理解我们其实是在按顺序“消费”两个数组中的元素直到找到目标位置。这为理解二分查找解法中“划分”的概念打下了基础。2.3 为何 O(log(mn)) 指向二分查找O(log N) 复杂度通常与“分而治之”、“每次操作将问题规模减半”的算法相关联最典型的就是二分查找。在一个长度为 N 的有序数组中查找目标我们每次比较中间元素就能排除掉一半的搜索空间。现在我们的“搜索空间”是什么不是某个具体的值而是中位数的位置或者说是那个能将两个数组合并序列完美划分为两半的“切割点”。关键洞察在于对于合并后的有序数组其中位数或用于计算中位数的两个数的位置是确定的。假设总长度total m n那么如果total是奇数中位数是第k total // 2 1小的数注意这里第1小指最小的数。如果total是偶数中位数是第k1 total // 2小的数和第k2 total // 2 1小的数的平均值。于是问题转化为如何在两个有序数组中找到第 k 小的数。而“寻找第 k 小的数”这个问题是可以通过在两个数组上协同进行二分查找来解决的并且可以达到 O(log(mn)) 的复杂度。更进一步的优化是我们可以在更短的数组上进行二分将复杂度降至 O(log(min(m, n)))这就是下面要详细解析的经典解法。3. 核心解法详解在两个数组上进行划分这个解法的核心思想可以概括为“割”或者“划分”。我们不去合并数组而是想象在两个数组上各切一刀将每个数组分成左右两部分。这两刀的位置共同决定了合并后数组的“左半部分”和“右半部分”。3.1 模型建立与符号定义让我们形式化地定义一下。假设我们在nums1上切一刀索引为ii的范围是0到m这意味着nums1的左半部分有i个元素nums1[0]...nums1[i-1]右半部分有m-i个元素nums1[i]...nums1[m-1]。同理在nums2上切一刀索引为j。我们的目标是让左半部分的总元素数等于右半部分的总元素数总数为偶数时或者左半部分比右半部分多一个总数为奇数时。也就是说我们需要满足i j (m n 1) // 2这里(m n 1) // 2是向上取整的除法它确保了当总数为奇数时左半部分多一个元素这个多出来的元素就是中位数。更重要的是我们必须保证左半部分的所有元素都小于等于右半部分的所有元素。由于数组各自有序我们只需要检查两个数组在切割点两侧元素的大小关系即可nums1[i-1] nums2[j]nums2[j-1] nums1[i]如果这两个条件都满足那么我们就找到了一个完美的划分。此时合并后的左半部分的最大值和右半部分的最小值就围绕着中位数。3.2 二分查找“割”的位置我们如何找到这样的i和j呢注意一旦i确定了根据等式i j (m n 1) // 2j也就确定了j (m n 1) // 2 - i。因此我们只需要在一个数组通常选择较短的那个以减少搜索范围上二分查找这个i的位置。为什么选择较短的数组进行二分假设m n我们选择在nums1上搜索i。搜索范围是[0, m]。i为 0 表示nums1的所有元素都在右半部分即“割”在数组最左边i为m表示nums1的所有元素都在左半部分即“割”在数组最右边。在较短的数组上二分时间复杂度是 O(log(min(m, n)))比在长数组上二分更优。二分查找的过程如下设left 0,right mm是较短数组的长度。计算i (left right) // 2。根据公式计算j (m n 1) // 2 - i。现在我们有四个关键值nums1[i-1],nums1[i],nums2[j-1],nums2[j]。注意i或j可能为 0 或等于数组长度这意味着某个数组的左半部分或右半部分可能为空我们需要在比较时进行特殊处理视为无穷小或无穷大。检查条件如果nums1[i-1] nums2[j]说明nums1的左半部分最大值太大了我们的“割”i应该向左移动即减小i以减小nums1左半部分的值。因此调整right i - 1。如果nums2[j-1] nums1[i]说明nums2的左半部分最大值太大了我们的“割”i应该向右移动即增大i以增大nums1右半部分的值从而让nums2的左半部分相对变小。因此调整left i 1。如果上述两个条件都不满足即nums1[i-1] nums2[j]且nums2[j-1] nums1[i]那么我们就找到了完美的划分。根据找到的完美划分计算中位数左半部分的最大值为max_left max(nums1[i-1], nums2[j-1])需处理边界。右半部分的最小值为min_right min(nums1[i], nums2[j])需处理边界。如果(m n)是奇数中位数就是max_left。如果(m n)是偶数中位数就是(max_left min_right) / 2.0。3.3 边界条件处理的魔鬼细节这个算法的实现难点几乎全在边界条件的处理上。下面这个表格总结了当i,j处于边界时对应值应该如何取值索引位置nums1[i-1]nums1[i]nums2[j-1]nums2[j]处理方式i 0不存在nums1[0]nums2[j-1]nums2[j]nums1_left_max -infi mnums1[m-1]不存在nums2[j-1]nums2[j]nums1_right_min infj 0nums1[i-1]nums1[i]不存在nums2[0]nums2_left_max -infj nnums1[i-1]nums1[i]nums2[n-1]不存在nums2_right_min inf在代码中我们通常用float(-inf)表示负无穷float(inf)表示正无穷。这样在比较max_left max(A[i-1], B[j-1])时如果其中一个不存在为负无穷那么结果自然就是另一个值。同理求min_right时也一样。注意一个非常关键的细节是在计算j时我们使用了(m n 1) // 2 - i。这个1确保了当总长度为奇数时左半部分比右半部分多一个元素。这使得我们最后可以直接用max_left作为奇数情况下的中位数而无需再取min_right。这是整个算法保持简洁优雅的重要一环。4. 完整代码实现与逐行解析理解了原理和边界条件后我们来看具体的代码实现。这里以 Python 为例因为它语法清晰易于理解算法逻辑。class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float: # 确保 nums1 是较短的数组方便在短数组上二分 if len(nums1) len(nums2): nums1, nums2 nums2, nums1 m, n len(nums1), len(nums2) total_left (m n 1) // 2 # 左半部分应有的元素个数 left, right 0, m # 在 nums1 上二分的边界i 的范围是 [0, m] while left right: # i 是 nums1 左半部分的元素个数 i (left right) // 2 # j 是 nums2 左半部分的元素个数由总左半部分数减去 i 得到 j total_left - i # 处理边界情况当 i/j 为 0 或 m/n 时对应的值为无穷小/大 nums1_left_max float(-inf) if i 0 else nums1[i - 1] nums1_right_min float(inf) if i m else nums1[i] nums2_left_max float(-inf) if j 0 else nums2[j - 1] nums2_right_min float(inf) if j n else nums2[j] # 二分查找的核心判断逻辑 if nums1_left_max nums2_right_min: # nums1 的左半部分太大需要减小 i即向左移动“割” right i - 1 elif nums2_left_max nums1_right_min: # nums2 的左半部分太大需要增大 i即向右移动“割” left i 1 else: # 条件满足找到了完美的划分 # 计算左半部分的最大值即可能的中位数奇数情况 max_of_left max(nums1_left_max, nums2_left_max) # 如果总长度是奇数中位数就是左半部分的最大值 if (m n) % 2 1: return max_of_left # 如果总长度是偶数中位数是左半部分最大值和右半部分最小值的平均 min_of_right min(nums1_right_min, nums2_right_min) return (max_of_left min_of_right) / 2.0 # 理论上循环内一定会返回这里返回 0.0 仅为了语法完整 return 0.0逐行解析与关键点交换数组第4-5行这是一个重要的优化和简化技巧。通过确保nums1是较短的数组我们二分查找的区间长度就是m较小值将时间复杂度稳定在 O(log(min(m, n)))。同时这也简化了后续边界条件的处理因为j的计算公式total_left - i确保了j不会为负数因为i m n且total_left约等于(mn)/2。total_left的计算第7行(m n 1) // 2是向上取整。无论总数奇偶total_left都代表了合并数组“左半部分”应有的长度。当总数为奇数时中位数包含在左半部分左半部分多一个当总数为偶数时中位数是左半部分最大值和右半部分最小值的平均。这个定义让后续处理变得统一。二分循环第10行标准的二分查找框架。left和right定义了i的所有可能位置。计算i和j第12-14行i是二分搜索的变量j是根据i推导出来的。这体现了“一个变量控制另一个变量随之确定”的思想。处理四个关键值的边界第17-20行这是算法的核心难点之一。使用float(‘-inf’)和float(‘inf’)来优雅地处理数组边界使得后续的大小比较逻辑可以统一无需写大量的if-else分支。例如当i 0时nums1的左半部分为空我们认为它的最大值是负无穷这样在max(nums1_left_max, nums2_left_max)时结果必然是nums2_left_max。二分判断条件第23-28行if nums1_left_max nums2_right_min:这对应着原理部分nums1[i-1] nums2[j]的情况。nums1左半部分的最大值竟然大于nums2右半部分的最小值这说明nums1的“割”太靠右了左半部分包含了太大的数。为了满足“左半部分所有元素 右半部分所有元素”我们必须把nums1的“割”向左移即减小i。elif nums2_left_max nums1_right_min:这对应着nums2[j-1] nums1[i]的情况。同理这说明nums2的“割”太靠左了或者说nums1的“割”太靠左了导致nums2左半部分的最大值偏大。我们需要将nums1的“割”向右移即增大i让nums1提供更多右半部分的小数来“平衡”nums2的左半部分。找到中位数并返回第30-36行当两个条件都不满足时划分完美。根据总长度的奇偶性返回结果。注意在偶数情况下我们取的是max_of_left和min_of_right的平均值这正是中位数的定义。5. 算法复杂度分析与对比现在我们来详细分析一下这个经典解法的性能并与其他方法进行对比。时间复杂度O(log(min(m, n)))。因为我们在较短的数组上进行二分查找每次迭代将搜索范围减半。这是满足题目进阶要求 O(log(mn)) 的并且是更优的。空间复杂度O(1)。我们只使用了固定数量的额外变量left,right,i,j, 几个最大值/最小值变量与输入数组的大小无关。为了更直观地理解不同解法的效率差异我们可以看下面的对比表格解法时间复杂度空间复杂度核心思想是否满足进阶要求适用场景合并后排序O((mn) log(mn))O(mn)暴力合并通用排序否快速实现不关心效率双指针归并不合并O(mn)O(1)模拟归并计数到中位否中等规模数据编码简单二分查找第k小数O(log(mn))O(1)递归排除 k/2 个元素是通用高效解法本文详解的划分法O(log(min(m, n)))O(1)在两个数组上协同二分划分是面试首选效率最高逻辑巧妙为什么划分法比“找第k小数”的二分法更优“找第k小数”的二分法也是一个经典的 O(log(mn)) 解法。其思路是每次比较两个数组第k/2小的元素并排除掉较小元素所在数组的前k/2个元素。虽然复杂度相同但划分法在代码实现上通常更简洁边界条件处理相对直观尤其是处理奇偶性时而且常数因子可能更小。划分法更直接地体现了“中位数”作为“划分”的本质属性因此在面试中更受青睐。6. 实战中的常见“坑”与调试技巧即便理解了算法亲手实现时还是可能掉进一些坑里。下面是我在多次练习和教学中总结出的常见问题。坑1索引计算错误导致数组越界这是最常见的问题。i和j的定义是“左半部分的元素个数”因此它们的取值范围是[0, m]和[0, n]。当i0时nums1[i-1]是无效访问。我们的代码通过预先判断并将其值设为无穷小来避免。务必在计算nums1[i-1],nums1[i],nums2[j-1],nums2[j]之前先检查i和j是否在边界上。坑2奇偶处理混乱中位数的定义因总元素个数奇偶而异。这个算法的巧妙之处在于通过total_left (m n 1) // 2这个向上取整的除法统一了奇偶情况。在奇数情况下中位数就是max_of_left在偶数情况下中位数是(max_of_left min_of_right) / 2。很多自己推导的实现容易在这里出错例如在奇数情况下错误地尝试去取min_of_right。坑3二分查找循环条件与更新逻辑标准的二分查找是while left right:更新时是left mid 1或right mid - 1。在这个问题里mid就是i。一定要确保在nums1_left_max nums2_right_min时更新right i - 1因为当前i太大了在nums2_left_max nums1_right_min时更新left i 1因为当前i太小了。方向搞反会导致死循环或找不到解。调试技巧小数据手动模拟用两个极小的数组例如[1]和[2]或者[1,3]和[2]在纸上一步步画出i,j计算四个关键值走一遍二分判断的流程。这是理解算法最有效的方式。打印关键变量在循环内部打印left,right,i,j,nums1_left_max,nums1_right_min,nums2_left_max,nums2_right_min的值。观察它们的变化是否符合预期。测试边界用例务必测试以下情况一个数组为空。两个数组等长且元素交错。一个数组的所有元素都小于另一个数组的所有元素。两个数组有重复元素。使用力扣的测试用例力扣的测试用例覆盖很全提交后如果出错仔细查看第一个出错的用例它往往能揭示你逻辑中的盲点。7. 举一反三算法思想的延伸应用解决这个问题所运用的“划分”和“协同二分”思想并不仅限于寻找中位数。它是一类“在两个有序数组中寻找特定分位点或第k元素”问题的通用框架。掌握这个思想你可以解决一系列变种问题。变种1寻找两个有序数组的第k小元素这是最直接的延伸。我们不再固定total_left为(mn1)//2而是令total_left k。算法流程完全不变最终当找到完美划分时第k小的元素就是左半部分的最大值max_of_left。因为此时左半部分恰好包含了合并后数组的前k个元素。变种2寻找两个有序数组的特定分位数例如上四分位数分位数可以转化为第k小问题。例如上四分位数75%位置就是第0.75 * (mn)小的数可能需要取整或插值。算法框架依然适用。变种3多个有序数组的中位数/第k小元素当数组数量超过两个时问题复杂度急剧上升。一种思路是使用多指针归并最小堆来达到 O(k log N) 的复杂度N为数组个数。另一种更优的思路是二分答案猜测一个中位数候选值mid然后在每个数组中用二分查找统计小于等于mid的元素个数总和如果等于目标排名就找到了。这种方法的时间复杂度是 O(N log C)其中 C 是数值范围。这体现了二分查找思想的另一种强大应用在答案的可能范围内进行二分。思想升华从“索引二分”到“值域二分”我们刚才讨论的划分法是在数组的“索引”上进行二分i是索引。而解决多个数组中位数问题的“二分答案”法是在“值域”上进行二分。这给了我们一个重要启示当直接寻找目标对象的“位置”很困难时可以转而判断一个“候选值”是否满足条件并通过二分搜索不断逼近这个候选值。这种“值域二分”或“二分答案”的技巧在解决“第k大”、“满足某种条件的最小/最大值”一类问题时非常有效。回到力扣第4题它之所以经典就是因为它完美融合了有序数组、二分查找、分治思想以及严谨的边界处理。它不要求你写出多么复杂的代码但要求你对算法有深刻的理解和清晰的逻辑。在面试中即使你不能一次性写出完美代码如果能清晰地阐述这个“划分”模型和二分查找的思路并正确地分析出边界情况也已经能获得面试官的高度认可了。