4. 寻找两个有序数组的中位数.md

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0 示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

思路：

方法一： O(m + n)，每个都遍历一次 方法二： O(m + n)，双指针，遍历到中位数 方法三： O(log(n + m))，转换为求第k小的数

solution:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const len1 = nums1.length
    const len2 = nums2.length
    const left = (len1 + len2 + 1) >> 1
    const right = (len1 + len2 + 2) >> 1
    return (getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, left) + getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, right)) * 0.5
    function getKth (arr1, s1, e1, arr2, s2, e2, k) {
        const l1 = e1 - s1 + 1
        const l2 = e2 - s2 + 1
        const mid = k >> 1
        const i = s1 + Math.min(l1, mid) - 1
        const j = s2 + Math.min(l2, mid) - 1
        if (l1 > l2) return getKth(arr2, s2, e2, arr1, s1, e1, k)
        else if (l1 === 0) return arr2[s2 + k - 1]
        else if (k === 1) return Math.min(arr1[s1], arr2[s2])
        else if (arr1[i] > arr2[j]) return getKth(arr1, s1, e1, arr2, j + 1, e2, k - (j - s2 + 1))
        else return getKth(arr1, i + 1, e1, arr2, s2, e2, k - ( i - s1 + 1 ))
    }
};