Median of Two Sorted Arrays

Difficulty: Hard

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).

Example

Input: nums1 = [1, 3], nums2 = [2]
Output: 2.0
Explanation: The merged array is [1, 2, 3] and the median is 2.

Brute-force approach

Merge both sorted arrays into one sorted array, then directly find the median from the merged array.

Steps

  1. Merge nums1 and nums2 into a single sorted array
  2. If total length is odd: return the middle element
  3. If total length is even: return the average of the two middle elements

Time complexity: O(m + n) · Space complexity: O(m + n)

Trade-offs

  • Merging takes O(m+n) time — doesn't meet the O(log(m+n)) requirement
  • Uses O(m+n) extra space for the merged array
  • Processes every element when we only need elements near the median

Optimal approach

Key insight: Instead of merging, we find a partition that splits both arrays so that exactly half the total elements are on the left. Binary search on the shorter array finds this partition in O(log(min(m, n))).

Binary search on the shorter array to find the correct partition point that divides both arrays into left and right halves such that all left elements are <= all right elements.

Steps

  1. Ensure nums1 is the shorter array
  2. Binary search: left=0, right=m
  3. For each i, compute j = (m+n+1)/2 - i
  4. Check partition validity using boundary elements
  5. If valid: compute median from boundary elements
  6. If leftMax1 > rightMin2: right = i-1
  7. If leftMax2 > rightMin1: left = i+1

Time complexity: O(log(min(m, n))) · Space complexity: O(1)