LeetCode #4. Median of Two Sorted Arrays

findMedianSortedArrays.js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(A, B) {     
    //確保A > B    
    if(A.length < B.length){
        let tmp = A;
        A = B;
        B = tmp;
    }
    
    let lenA = A.length,
        lenB = B.length,
        len = lenA + lenB,
        start = 0,
        end = lenA - 1;
    
    if(lenB != 0){        
        //先猜頭尾
        if(A[start] > B[lenB - 1]){
            end = -1;
        }else if(A[end] < B[0]){
            start = end;
        }
        
        let index = start;
        for(let i = 0; i < B.length; i++){
            index = binarySearch(A, B[i], index, end);//動態index起始值
            //插入至A
            A.splice(index, 0, B[i]);
            end++;
        }
    }
        
    let half = len >> 1;
    
    return len % 2 == 1 ?
        //odd
        A[half]:
        //even
        (A[half] + A[half - 1]) / 2;
    
    function binarySearch(arr, target, start, end){
        while(start <= end){
            let mid = (start + end) >> 1;
            
            if(arr[mid] == target){
                return mid;
            }
            
            if(target > arr[mid]){
                start = mid + 1;
            }
            
            if(target < arr[mid]){
                end = mid - 1;                
            }
        }
        
        return start;
    };   
};