【4】寻找两个正序数组的中位数：困难

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/。 数组、二分查找、分治算法

如果对时间复杂度的要求中有 log，那么一半都使用二分查找

基础

直接想到的，很简单但是不符合题目要求，时间复杂度为 (m + n)

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    let nums = [...nums1, ...nums2]
    nums.sort((a, b) => a - b);
    let len = nums.length;
    return len % 2 === 1 ? nums[(len - 1) / 2] : (nums[len / 2 - 1] + nums[len / 2]) / 2
};

二分查找

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    let len = nums1.length + nums2.length;
    let k = Math.ceil(len / 2);
    return len % 2 === 1 ? getKthElement(nums1, nums2, k) : (getKthElement(nums1, nums2, k) + getKthElement(nums1, nums2, k + 1)) / 2
};

// 找到第 K 小数
function getKthElement(nums1: number[], nums2: number[], k: number): number {
    const len1 = nums1.length;
    const len2 = nums2.length;
    let index1 = 0;
    let index2 = 0;

    while(true) {
        // 边界情况
        if (index1 === len1) {
            return nums2[index2 + k - 1]
        }
        if (index2 === len2) {
            return nums1[index1 + k - 1] 
        }
        if (k === 1) {
            return Math.min(nums1[index1], nums2[index2])
        }

        let half = Math.floor(k / 2)
        let newIndex1 = Math.min(index1 + half, len1) - 1;
        let newIndex2 = Math.min(index2 + half, len2) - 1;
        if(nums1[newIndex1] <= nums2[newIndex2]) {
            k -= (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1
        } else {
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 1;
        }
    }
}