NeetCode #299LC-4HardBinary SearchNC 150NC 250
← Back to All Problems#299 · #4 · Median of Two Sorted Arrays(寻找两个正序数组的中位数)
📌 Problem Statement & Constraints
Given two sorted arrays
nums1 and nums2, return the median of the combined array. The overall run time must be O(log(m + n)). Constraints: 0 <= m, n <= 1000, 1 <= m + n, -10^6 <= nums[i] <= 10^6.💡 Core Algorithmic Approaches
- The median splits the combined array into a left half and a right half of (almost) equal size.
- Binary search for the partition point in the shorter array; the partition in the longer array follows from the required half size.
- A partition is valid when the largest element on the left is at most the smallest on the right, across both arrays.
- Sentinel values (
-inf/+inf) handle the partitions at the extreme ends, eliminating boundary special cases.
💻 Benchmark Python3 Implementation
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# binary search on the shorter array
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = total // 2
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # elements taken from nums1
j = half - i # elements taken from nums2
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 <= right2 and left2 <= right1:
if total % 2:
return min(right1, right2)
return (max(left1, left2) + min(right1, right2)) / 2
if left1 > right2:
hi = i - 1 # take fewer from nums1
else:
lo = i + 1 # take more from nums1
return 0.0⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log(min(m, n))): binary search over the shorter array.
💾 Space Complexity
O(1): a few indices and sentinels.
⚠️ Interview Pitfalls & Follow-ups
- Binary searching over the longer array: still correct but slower; always pick the shorter one so the partition range is minimal.
- Forgetting the sentinels: without
-inf/+inf, thei == 0andj == 0cases need separate branches, which is where bugs live. - Using the wrong half size for odd totals:
half = total // 2puts the extra element on the right, so the odd case returnsmin(right1, right2). - Merging the arrays first: O(m + n) time and space, which the problem's complexity requirement forbids.
- Computing the median as
(left + right) / 2with integer division: the result is a float and Python's/is correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Binary Search Problems
中文速览与面试要点
寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n))。约束:nums1.length == m;nums2.length == n;0 ≤ m, n ≤ 1000;1 ≤ m + n ≤ 2000;-10^6 ≤ nums1[i], nums2[i] ≤ 10^6。
核心要点
- 对「划分位置」二分(标准解) :在较短数组上二分划分点 i,把两个数组都切成「左半」与「右半」,使左半元素总数恰好为 (m+n+1)//2 。
- 划分的合法性条件 : max(左半) <= min(右半) ,即 left1 <= right2 且 left2 <= right1 。
- 收缩规则 :若 left1 > right2 ,说明 nums1 的划分点太靠右,令 r = i − 1 ;若 left2 > right1 ,说明太靠左,令 l = i + 1 。
- 取中位数 :总长度为奇数时答案为 max(left1, left2) ;偶数时为 (max(left1, left2) + min(right1, right2)) / 2 。
- 哨兵技巧 :当 i = 0 时 left1 = −∞ ;i = m 时 right1 = +∞ 。这样无需为边界写特判。
常见陷阱
- 在较长的数组上二分 :复杂度会变成 O(log(max(m, n))),且 j 可能越界(因为 half − i 需要落在 [0, n] 内)。必须先交换保证 nums1 较短。
- 忘记哨兵导致边界越界 :i = 0 时 nums1[i−1] 会取到最后一个元素(Python 负下标静默生效),产生错误结果而不报错——这是本题最隐蔽的坑。必须用 ±∞ 哨兵。
- half 的取法写成 total // 2 :应为 (total + 1) // 2 ,保证左半元素数 ≥ 右半,这样奇数长度时中位数恰好在左半的最大值。
- 偶数长度时返回 (max(left1, left2) + min(right1, right2)) / 2 忘记转 float :Python 3 的 / 自动返回 float,但若用 // 会丢失精度。
- 用「归并后取中位数」 :O(m + n) 时间、O(m + n) 空间,不满足题目要求的 O(log(m+n))。
参考实现
class Solution:
def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
# 保证在较短的数组上二分,使复杂度为 O(log(min(m, n)))
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = (total + 1) // 2 # 左半应有的元素个数
l, r = 0, m # 在 nums1 上二分「取前几个元素进左半」
while l <= r:
i = (l + r) // 2 # nums1 左半取前 i 个
j = half - i # nums2 左半取前 j 个
left1 = nums1[i - 1] if i > 0 else float('-inf')
right1 = nums1[i] if i < m else float('inf')
left2 = nums2[j - 1] if j > 0 else float('-inf')
right2 = nums2[j] if j < n else float('inf')
if left1 <= right2 and left2 <= right1:
# 划分合法
if total % 2 == 1:
return float(max(left1, left2))
return (max(left1, left2) + min(right1, right2)) / 2.0
elif left1 > right2:
r = i - 1 # nums1 划分太靠右
else:
l = i + 1 # nums1 划分太靠左
return 0.0