两个有序数组的中位数
在较短数组的分割边界上进行二分查找，以 O(log(min(m,n))) 的时间解决两个有序数组的中位数问题。
两个有序数组的中位数 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
两个有序数组的中位数
两个有序数组的中位数（LeetCode 4）是一道经典的困难题。给定两个有序数组 nums1（长度为 m）和 nums2（长度为 n），要求在 O(log(min(m,n))) 时间内找出它们合并后有序序列的中位数。朴素方法是在 O(m+n) 时间内合并两个数组，但最优解法是在分割边界上进行二分查找。这是顶尖科技公司最常考的困难题之一。
# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0
nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5
print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))朴素合并方法
最简单的 O(m+n) 方法是：合并两个有序数组，然后找出中位数。合并两个有序数组需要 O(m+n)。长度为 L 的数组的中位数为：当 L 为奇数时是 arr[L//2]；当 L 为偶数时是 (arr[L//2-1] + arr[L//2]) / 2。这种方法是正确的，但无法满足 O(log(min(m,n))) 的要求。在面试中，应先介绍这种方法以建立基准方案，然后再进行优化。
def find_median_naive(nums1, nums2):
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i]); i += 1
else:
merged.append(nums2[j]); j += 1
merged += nums1[i:] + nums2[j:]
L = len(merged)
if L % 2 == 1:
return float(merged[L // 2])
return (merged[L//2 - 1] + merged[L//2]) / 2.0
print(find_median_naive([1,3],[2])) # 2.0
print(find_median_naive([1,2],[3,4])) # 2.5分割思想
关键洞见是：中位数会将合并后的数组分成大小相等的两半。我们需要分别在 nums1 和 nums2 中找到一个分割，使得：(1) 左半部分的总大小与右半部分相同。(2) 左半部分的所有元素都 ≤ 右半部分的所有元素。如果对 nums1 中正确的分割点进行二分查找，那么 nums2 中的分割点就会由总长度约束自动确定。
# Partition concept visualised:
# nums1: [1, 3] | [5, 7] (partition after index 1)
# nums2: [2, 4] | [6, 8] (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5
nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])在分割点上进行二分查找
在较短数组 nums1 的分割索引 i 上进行二分查找。nums2 中的分割索引 j 由 j = (m+n+1)//2 - i 确定（确保左半部分包含 (m+n+1)//2 个元素）。当 nums1[i-1] ≤ nums2[j] 且 nums2[j-1] ≤ nums1[i] 时，分割是有效的。二分查找会将 i 向上或向下调整，以找到平衡点。
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is the shorter array
if len(nums1) > len(nums2):
return find_median_sorted_arrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # partition index in nums1
j = (m + n + 1) // 2 - i # partition index in nums2
# Boundary values with sentinels
max_left1 = float('-inf') if i == 0 else nums1[i-1]
min_right1 = float('inf') if i == m else nums1[i]
max_left2 = float('-inf') if j == 0 else nums2[j-1]
min_right2 = float('inf') if j == n else nums2[j]
if max_left1 <= min_right2 and max_left2 <= min_right1:
# Found the correct partition
if (m + n) % 2 == 1:
return float(max(max_left1, max_left2))
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
elif max_left1 > min_right2:
hi = i - 1 # i is too large, move left
else:
lo = i + 1 # i is too small, move right
return 0.0
print(find_median_sorted_arrays([1,3],[2])) # 2.0
print(find_median_sorted_arrays([1,2],[3,4])) # 2.5跟踪二分查找
跟踪 nums1=[1,3], nums2=[2]：m=2，n=1，total=3，lo=0，hi=2。i=(0+2)//2=1，j=(2+1+1)//2-1=1。max_left1=nums1[0]=1，min_right1=nums1[1]=3，max_left2=nums2[0]=2，min_right2=inf（j=1=n）。检查：1≤inf 且 2≤3 ✓。总长度为奇数：返回 max(1,2)=2.0。✓ 由于数组长度较小，算法在第一步就找到了分割。
def find_median_traced(nums1, nums2):
if len(nums1) > len(nums2):
return find_median_traced(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
step = 0
while lo <= hi:
step += 1
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
ml1 = float('-inf') if i==0 else nums1[i-1]
mr1 = float('inf') if i==m else nums1[i]
ml2 = float('-inf') if j==0 else nums2[j-1]
mr2 = float('inf') if j==n else nums2[j]
print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
print(find_median_traced([1,3],[2]))为什么要在较短数组上进行二分查找
我们在较短的数组上进行二分查找，以实现 O(log(min(m,n)))，而不是 O(log(m+n))。较长数组的分割完全由较短数组的分割决定。如果 len(nums1) > len(nums2)，就交换输入，从而确保较短数组始终是搜索空间。不变量是：当 j 根据 i 和总长度推导出来时，j 始终是 nums2 的有效分割索引。
# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)
m, n = 3, 5 # m <= n
half = (m+n+1)//2
for i in range(m+1):
j = half - i
valid = 0 <= j <= n
print(f'i={i}: j={j}, valid={valid}')处理偶数和奇数总长度
当合并后的长度为奇数时：中位数是左半部分的最大值（max(max_left1, max_left2)）。当长度为偶数时：中位数是左半部分最大值与右半部分最小值的平均值。用于计算左半部分大小的 (m+n+1)//2 公式对两种情况都适用：当总长度为偶数时，它会使左侧多出一个元素，然后与 min_right 求平均，从而得到偶数长度数组的中位数。
def median_demo(a, b):
merged = sorted(a + b)
L = len(merged)
expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
computed = find_median_sorted_arrays(a[:], b[:])
print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
assert abs(expected - computed) < 1e-9
def find_median_sorted_arrays(nums1, nums2):
if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
m,n=len(nums1),len(nums2); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[]) # single array边界情况
关键边界情况包括：(1) 一个数组为空——中位数就是非空数组的中位数。(2) 一个数组的所有元素都小于另一个数组的元素——分割点位于某个极端位置。(3) 存在重复元素——算法可以自然处理。(4) 两个数组的长度都为 1——这是一个简单的双元素中位数问题。编写代码后，务必测试这些情况。使用哨兵值 -∞ 和 +∞ 可以简洁地处理边界分割（i=0 或 i=m）。
def fmsa(a,b):
if len(a)>len(b): return fmsa(b,a)
m,n=len(a),len(b); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
# Edge cases
print(fmsa([], [1])) # 1.0
print(fmsa([2], [])) # 2.0
print(fmsa([1,2], [3,4])) # 2.5
print(fmsa([3,4], [1,2])) # 2.5
print(fmsa([1,1,1], [1,1])) # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35])) # 17.5推广：两个数组中的第 k 小元素
中位数问题可以推广为寻找两个有序数组中的第 k 小的元素。每一步都比较两个数组中第 k//2 个元素。舍弃较小的一半：这 k//2 个元素都小于第 k 个元素，因此可以将它们丢弃。将 k 减少 k//2，然后递归处理。基本情况包括：一个数组为空（返回另一个数组中的第 k 个元素），或 k=1（返回两个数组首端元素中的较小值）。时间复杂度：O(log k) = O(log(m+n))。
def kth_smallest(nums1, nums2, k):
if not nums1: return nums2[k-1]
if not nums2: return nums1[k-1]
if k == 1: return min(nums1[0], nums2[0])
# Compare k//2-th elements
half = k // 2
i = min(half, len(nums1)) - 1 # index in nums1
j = min(half, len(nums2)) - 1 # index in nums2
if nums1[i] <= nums2[j]:
# Eliminate first (i+1) elements of nums1
return kth_smallest(nums1[i+1:], nums2, k - (i+1))
else:
return kth_smallest(nums1, nums2[j+1:], k - (j+1))
nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')比较所有方法
最终对比：合并数组：O(m+n) time，O(m+n) 空间。对分割进行二分查找：O(log(min(m,n))) time，O(1) 空间。第 k 小元素递归：O(log(m+n)) time，调用栈空间为 O(log k)。对于这个问题，面试官期望使用对分割进行二分查找的方法。这是常见 LeetCode 问题中最难清晰讲解的一道——请练习分割逻辑和四个边界检查，直到能够熟练地完成它们。
# Performance comparison
import time, random
def merge_median(a, b):
merged = sorted(a+b)
L=len(merged)
return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
def binary_median(a, b):
if len(a)>len(b): return binary_median(b,a)
m,n=len(a),len(b);lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2;j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
for size in [100, 10000]:
a = sorted(random.sample(range(size*2), size))
b = sorted(random.sample(range(size*2), size))
t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')面试沟通策略
面试中遇到这道难题时：(1) 立即说明朴素的 O(m+n) 合并方法——这能体现您的能力。(2) 解释 O(log(min(m,n))) time 的目标和分割思路。(3) 逐步说明分割不变式：左侧最大值1 ≤ 右侧最小值2 且左侧最大值2 ≤ 右侧最小值1。(4) 明确处理哨兵值。(5) 说明奇数和偶数情况下的中位数公式。(6) 使用 1～2 个示例进行测试。即使面对很少有候选人能在压力下完美解决的问题，这个 5 步框架也能体现系统化的问题解决能力。
# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
return findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
max_l1 = nums1[i-1] if i > 0 else float('-inf')
min_r1 = nums1[i] if i < m else float('inf')
max_l2 = nums2[j-1] if j > 0 else float('-inf')
min_r2 = nums2[j] if j < n else float('inf')
if max_l1 <= min_r2 and max_l2 <= min_r1:
if (m + n) % 2:
return float(max(max_l1, max_l2))
return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
elif max_l1 > min_r2: hi = i - 1
else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2])) # 2.0
print(findMedianSortedArrays([1,2],[3,4])) # 2.5快速检查
请测试您对本课数据结构 & 算法——编程面试准备相关概念的理解。
课程回顾
本课中您学到了：可以通过在较短数组中对正确的分割边界进行二分查找，以 O(log(min(m,n))) 找到两个有序数组的中位数；当左侧最大值1 ≤ 右侧最小值2 且左侧最大值2 ≤ 右侧最小值1 时，分割才有效，并使用哨兵值处理边界情况；以及第 k 小元素的推广使用递归式的半区间消除方法，在 O(log k) time 内完成。恭喜您完成分治课程！现在，您已经拥有一套全面的编程面试工具。
常见问题解答
「两个有序数组的中位数」课时是免费的吗？
是的 — 「两个有序数组的中位数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「两个有序数组的中位数」这节课中我会学到什么？
在较短数组的分割边界上进行二分查找，以 O(log(min(m,n))) 的时间解决两个有序数组的中位数问题。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「两个有序数组的中位数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 分治模板
- 使用修改后的归并排序统计逆序对
- 多数元素：Boyer-Moore 投票法
- 两个有序数组的中位数