4. Median of Two Sorted Arrays

Description

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 1:

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

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

 

Solutions

Solution: Binary Search

• Time complexity: O(log(m+n))
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = function (nums1, nums2) {
  const m = nums1.length;
  const n = nums2.length;
  const medianKthA = Math.floor((m + n + 1) / 2);
  const medianKthB = Math.floor((m + n + 2) / 2);
  const findKth = (a, b, kth) => {
    if (a >= m) return nums2[b + kth - 1];
    if (b >= n) return nums1[a + kth - 1];
    if (kth === 1) return Math.min(nums1[a], nums2[b]);
    const mid = Math.floor(kth / 2);
    const mid1 = a + mid - 1;
    const mid2 = b + mid - 1;
    const midValue1 = mid1 < m ? nums1[mid1] : Number.MAX_SAFE_INTEGER;
    const midValue2 = mid2 < n ? nums2[mid2] : Number.MAX_SAFE_INTEGER;

    return midValue1 < midValue2 ? findKth(a + mid, b, kth - mid) : findKth(a, b + mid, kth - mid);
  };

  return (findKth(0, 0, medianKthA) + findKth(0, 0, medianKthB)) / 2;
};