4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be $O(\log{(m+n)})$.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3) / 2 = 2.5

Solution: Binary Search

Python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        def find_kth(k, idx1=0, idx2=0):
            half = k / 2 or 1
            mid1 = idx1 + half - 1
            mid2 = idx2 + half - 1
            num1 = nums1[mid1] if mid1 < len(nums1) else float('inf')
            num2 = nums2[mid2] if mid2 < len(nums2) else float('inf')
            if k <= 1:
                return min(num1, num2)
            if num1 <= num2:
                return find_kth(k - half, idx1 + half, idx2)
            return find_kth(k - half, idx1, idx2 + half)

        total = len(nums1) + len(nums2)
        if total % 2 == 1:
            mid = (total + 1) / 2
            return find_kth(mid)
        mid = total / 2
        return (find_kth(mid) + find_kth(mid + 1)) / 2.0

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = (nums1, nums2) => {
  const findKth = (k, idx1 = 0, idx2 = 0) => {
    const half = Math.trunc(k / 2) || 1;
    const mid1 = idx1 + half - 1;
    const mid2 = idx2 + half - 1;
    const num1 = mid1 < nums1.length ? nums1[mid1] : Infinity;
    const num2 = mid2 < nums2.length ? nums2[mid2] : Infinity;
    if (k <= 1) {
      return Math.min(num1, num2);
    }
    if (num1 <= num2) {
      return findKth(k - half, idx1 + half, idx2);
    }
    return findKth(k - half, idx1, idx2 + half);
  };

  const total = nums1.length + nums2.length;
  if (total % 2 === 1) {
    const mid = (total + 1) / 2;
    return findKth(mid);
  }
  const mid = total / 2;
  return (findKth(mid) + findKth(mid + 1)) / 2;
};

Lessons:

• Use find_kth to find median.
• Use binary search to find kth.