用二分法寻找两个正序数组的中位数

[TieMuZhen]

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
function getKthElement(nums1, nums2, k){
    let length1 = nums1.length,
        length2 = nums2.length,
        p1 = 0,
        p2 = 0;
    while(true){
        if(p1 == length1) {
            return nums2[p2 + k  - 1]; // 因为下面代码中的p1是从下一个位置开始的，所以这里要-1
        }else if(p2 == length2){
            return nums1[p1 + k - 1];
        }else if(k == 1){
            return Math.min(nums1[p1], nums2[p2]);
        }
        let mid = Math.floor(k / 2);
        let newP1 = Math.min(p1 + mid - 1, length1 - 1);
        let newP2 = Math.min(p2 + mid - 1, length2 - 1);
        let val1 = nums1[newP1];
        let val2 = nums2[newP2];
        if(val1 <= val2){
            k -= newP1 - p1 + 1; // 减去找出的最小数字的个数
            p1 = newP1 + 1; // 更新指针为下一个
        }else{
            k -= newP2 - p2 + 1;
            p2 = newP2 + 1;
        }
    }
}
var findMedianSortedArrays = function(nums1, nums2) {
    let totalength = nums1.length + nums2.length;
    if(totalength % 2 == 1) { // 两数组总个数为奇数个
        let result = getKthElement(nums1, nums2, Math.floor(totalength / 2) + 1);
        return result;
    }else{
        let left = getKthElement(nums1, nums2, Math.floor(totalength / 2));
        let right = getKthElement(nums1, nums2, Math.floor(totalength / 2) + 1);
        return (left + right) / 2;
    }
};

题解

题解中的解法三