Q25: Median of Two Sorted Arrays

Find the median of two sorted arrays nums1 and nums2 in O(log(min(m, n))) time complexity using Binary Search partitioning.

Binary Search Partition Median Finder

function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1); // Ensure nums1 is smaller
  }
  
  const m = nums1.length;
  const n = nums2.length;
  let low = 0, high = m;
  
  while (low <= high) {
    const partitionA = Math.floor((low + high) / 2);
    const partitionB = Math.floor((m + n + 1) / 2) - partitionA;
    
    const maxLeftA = partitionA === 0 ? -Infinity : nums1[partitionA - 1];
    const minRightA = partitionA === m ? Infinity : nums1[partitionA];
    
    const maxLeftB = partitionB === 0 ? -Infinity : nums2[partitionB - 1];
    const minRightB = partitionB === n ? Infinity : nums2[partitionB];
    
    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
      if ((m + n) % 2 === 0) {
        return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
      } else {
        return Math.max(maxLeftA, maxLeftB);
      }
    } else if (maxLeftA > minRightB) {
      high = partitionA - 1;
    } else {
      low = partitionA + 1;
    }
  }
}

console.log(findMedianSortedArrays([1, 3], [2])); // 2.0

💡 Executes binary search on smaller array nums1 to find partition splits where left halves elements are smaller than right halves elements, giving median in O(log(min(m, n))) time.

Key Takeaways

Applies Binary Search on the smaller array to find a valid partition point.
Valid partition occurs when maxLeftA <= minRightB and maxLeftB <= minRightA.

Knowledge Check

Why is Binary Search performed specifically on the smaller of the two input arrays?

Q25: Median of Two Sorted Arrays

STAY UPDATED WITH BYTES!