4. Median of Two Sorted Arrays

Problem:

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:

O(log (m+n)) means half of the sequence is ruled out on each loop. So obviously we need binary search.

To do it on two sorted arrays, we need a formula to guide division.

Let nums3 be the sorted array combining all the items in nums1 and nums2.

If nums2[j-1] <= nums1[i] <= nums2[j], then we know nums1[i] is at num3[i+j]. Same goes nums1[i-1] <= nums2[j] <= nums1[i].

Let k be ⌊(m+n-1)/2⌋. We need to find nums3[k] (and also nums3[k+1] if m+n is even).

Let i + j = k, if we find nums2[j-1] <= nums1[i] <= nums2[j] or nums1[i-1] <= nums2[j] <= nums1[i], then we got k.

Otherwise, if nums1[i] <= nums2[j] then we know nums1[i] < nums2[j-1] (because we did not find k).

• There are i items before nums1[i], and j-1 items brefor nums2[j-1], which means nums1[0...i] are before nums3[i+j-1]. So we now know nums1[0...i] < nums3[k]. They can be safely discarded.

• We Also have nums1[i] < nums2[j], which means nums2[j...n) are after nums3[i+j]. So nums2[j...n) > nums3[k].

Same goes nums1[i-1] <= nums2[j] <= nums1[i].

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
let findMedianSortedArrays = function (nums1, nums2) {
  const mid = (nums1.length + nums2.length - 1) / 2 | 0

  if ((nums1.length + nums2.length) % 2 === 0) {
    return (_find(nums1, nums2, mid) + _find(nums1, nums2, mid + 1)) / 2
  }

  return _find(nums1, nums2, mid)
}


function _find (nums1, nums2, k) {
  if (nums1.length > nums2.length) {
    // So that the `i` below is always smalller than k,
    // which makes `j` always non-negative
    [nums1, nums2] = [nums2, nums1]
  }
  let s1 = 0
  let s2 = 0
  let e1 = nums1.length
  let e2 = nums2.length

  while (s1 < e1 || s2 < e2) {
    const i = s1 + ((e1 - s1) / 2 | 0)
    const j = k - i
    const ni = i >= e1 ? Infinity : nums1[i]
    const nj = j >= e2 ? Infinity : nums2[j]
    const ni_1 = i <= 0 ? -Infinity : nums1[i-1]
    const nj_1 = j <= 0 ? -Infinity : nums2[j-1]

    if (nj_1 <= ni && ni <= nj) {
      return ni
    }

    if (ni_1 <= nj && nj <= ni) {
      return nj
    }

    if (ni <= nj) {
      s1 = i + 1
      e2 = j
    } else {
      s2 = j + 1
      e1 = i
    }
  }
};