⚡Flashcard Drill➔
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

  1. The median splits the combined array into a left half and a right half of (almost) equal size.
  2. Binary search for the partition point in the shorter array; the partition in the longer array follows from the required half size.
  3. A partition is valid when the largest element on the left is at most the smallest on the right, across both arrays.
  4. 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, the i == 0 and j == 0 cases need separate branches, which is where bugs live.
  • Using the wrong half size for odd totals: half = total // 2 puts the extra element on the right, so the odd case returns min(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) / 2 with 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.
🎯 Drill This Card Now➔

🧩 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(左半) &lt;= min(右半) ,即 left1 &lt;= right2 且 left2 &lt;= right1 。
  • 收缩规则 :若 left1 &gt; right2 ,说明 nums1 的划分点太靠右,令 r = i − 1 ;若 left2 &gt; 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