💬 Discord
Sign In
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.