08. Median of Two Sorted Arrays

Difficulty:HardPattern:Binary Search PartitionTime:O(log(min(m, n)))Space:O(1)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays in $O(\log(\min(m, n)))$ time.

How It Works & Algorithmic Design

Solves using Binary Search Partitioning on Shorter Array:

Ensure Shorter Array: Swap arrays if nums1.length > nums2.length so nums1 is shorter.
Binary Search: Search partition point $i$ in nums1 between $0$ and $m$:
- Set j = Math.floor((m + n + 1) / 2) - i in nums2.
- Calculate boundary values: maxLeft1, minRight1, maxLeft2, minRight2.
Partition Check:
- If maxLeft1 <= minRight2 and maxLeft2 <= minRight1, valid median partition found!
- Odd combined length: median = Math.max(maxLeft1, maxLeft2).
- Even combined length: median = (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.
- If maxLeft1 > minRight2: move search left (high = i - 1).
- Else: move search right (low = i + 1).

Why This Approach Works Best

Halves partition choices on smaller array achieving optimal $O(\log(\min(m, n)))$ runtime.

Example Walkthrough

Input Arrays: nums1 = [1, 3], nums2 = [2]

Sorted arrays.

Merged Order: [1, 2, 3]

Median is middle element 2.

Output: 2.0

Combined median.

Answer: Median of Two Sorted Arrays implementation

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let low = 0, high = m;
  while (low <= high) {
    const i = Math.floor((low + high) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ? Infinity : nums1[i];
    const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ? Infinity : nums2[j];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      if ((m + n) % 2 === 1) return Math.max(maxLeft1, maxLeft2);
      return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
    } else if (maxLeft1 > minRight2) {
      high = i - 1;
    } else {
      low = i + 1;
    }
  }
  return 0.0;
}

💡 Binary search partition indices on shorter array to divide total elements into balanced left/right halves.

Key Takeaways

Always run binary search on the shorter array to ensure $O(\log(\min(m, n)))$ execution.
Use -Infinity and Infinity boundary sentinels to simplify edge partitions.
Requires no memory allocation ($O(1)$ space).