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;}}}

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆