4. Median of Two Sorted Arrays

Problem

https://leetcode.com/problems/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

One

O((m+n)/2) Direct Search

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    var len = Math.floor((nums1.length + nums2.length - 1) / 2)
    var p1 = 0
    var p2 = 0
    var num
    for (let i = 0; i < len; i += 1) {
        if (p1 >= nums1.length) {
            p2 += len - i
            break
        }
        if (p2 >= nums2.length) {
            p1 += len - i
            break
        }
        nums1[p1] < nums2[p2] ? ++p1 : ++p2
    }

    // len
    if (p1 >= nums1.length) {
        num = nums2[p2++]
    } else if (p2 >= nums2.length) {
        num = nums1[p1++]
    } else {
        num = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++]
    }

    if ((nums1.length + nums2.length) % 2 === 0) {
        // len + 1
        if (p1 >= nums1.length) {
            return (num + nums2[p2]) / 2
        } else if (p2 >= nums2.length) {
            return (num + nums1[p1]) / 2
        } else {
            return (num + (nums1[p1] < nums2[p2] ? nums1[p1] : nums2[p2])) / 2
        }
    }

    return num
};

Two

http://articles.leetcode.com/find-k-th-smallest-element-in-union-of/, where k = (m+n)/2.

Maintaining the invariant  
i + j = k – 1,

If Bj-1 <= Ai <= Bj, then Ai must be the k-th smallest,  
(because Ai <= Ai+1 && Ai <= Bj, so k = i + j + 1)

or else if Ai-1 <= Bj <= Ai, then Bj must be the k-th smallest.

If not satisfied, then Ai must be smaller than Bj-1 or larger than Bj.

If Ai < Bj-1, then Ai < kth < Bj-1. Because there are k elements in A0~Ai plus B0~Bj-1, Ai < Bj-1 means there are more elements in A that are between Ai and Bj-1. So the kth element must be larger than Ai, but smaller than Bj-1.

If Ai > Bj, then Bj < kth < Ai.

Same as Bj.

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {

    function findKthSmallest(n1, n2, k) {
        var i = Math.floor(k / 2)
        var j = k - 1 - i
        var ni = i === n1.length? Infinity: n1[i]
        var nj = j === n2.length? Infinity: n2[j]
        var ni_1 = i === 0? -Infinity: n1[i-1]
        var nj_1 = j === 0? -Infinity: n2[j-1]

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

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

        if (ni < nj) {
            return findKthSmallest(n1.slice(i+1), n2.slice(0, j), k-i-1)
        } else {
            return findKthSmallest(n1.slice(0, i), n2.slice(j+1), k-j-1)
        }
    }

    var mid = Math.floor((nums1.length + nums2.length + 1) / 2)
    if ((nums1.length + nums2.length) % 2 === 0) {
        return (findKthSmallest(nums1, nums2, 1) + findKthSmallest(nums1, nums2, 2)) / 2
    } else {
        return findKthSmallest(nums1, nums2, mid)
    }
};