计算两个有序数组的中位数

题目：

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

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

 

类比一个数组的中位数，求两个数组的中位数就相当于把两个数组合并后的一个数组的中位数，例

输入： num1=[1,3,5]  num2=[2,4,6]

输出：(3+4)/2=3.5

 

方法：二分+递归

思路：

--看到有序，并且明确要求时间复杂度为log级的，肯定需要二分。但是请注意，很多人一看到二分，就想也不想的开始对数组进行二分，但是对于这题，对数组二分就进了死胡同了。这题是对另一个量进行二分。

--再分析中位数的特征，就是求数组中的某一个(或两个)数，其左右两边的个数相等

--设两个有序数组分别为，a，长度m；b，长度n

--那么这个中位数，就是，a和b合并后的第(m+n+1)/2个(先不管有2个中位数的情况，后面会有个小技巧来屏蔽奇偶差异)

--那么现在的问题就变成了，求两个有序数组中，从小到大的第k个值

--所以二分其实是对k进行二分，两个数组同时从0开始，每次往后跳k/2个，当然不是同时跳，谁更小才能跳，保证已经跳过的数在整个数组中是最小的

 

NO BB，上代码，先写求第k个值的方法

private int findKth(int[] array1, int start1, int end1, int[] array2, int start2, int end2, int k){
        if(start1>end1){
            return array2[start2+k-1];
        }
        if(start2>end2){
            return array1[start1+k-1];
        }
        if(k==1){
            return Math.min(array1[start1], array2[start2]);
        }
        int mid1=Integer.MAX_VALUE;
        int mid2=Integer.MAX_VALUE;
        //这里的思想，其实不是每次移动整个end-start的一半，而是移动k的一半
        if(start1+k/2-1<=end1){
            mid1=array1[start1+k/2-1];
        }
        if(start2+k/2-1<=end2){
            mid2=array2[start2+k/2-1];
        }
        if(mid1<mid2){
            return findKth(array1, start1+k/2, end1, array2, start2, end2, k-k/2);
        }
        return findKth(array1, start1, end1, array2, start2+k/2, end2, k-k/2);
}

 

再写求中位数的方法

public double findMiddle(int[] array1, int[] array2){
        int totalLength=array1.length+array2.length;
        if(totalLength==0){
            return -1;
        }
        //屏蔽奇偶差异，当是奇数时，k1，k2找到的是同一个中位数；当是偶数时，k1，k2找到的是两个中位数
        int k1=(totalLength+1)/2;
        int k2=(totalLength+2)/2;
        int mid1, mid2;
        if(array1.length==0){
            mid1=array2[k1-1];
            mid2=array2[k2-1];
        }else if(array2.length==0){
            mid1=array1[k1-1];
            mid2=array1[k2-1];
        }else {
            mid1=findKth(array1, 0, array1.length-1, array2, 0, array2.length-1, k1);
            mid2=findKth(array1, 0, array1.length-1, array2, 0, array2.length-1, k2);
        }
        return (double) (mid1+mid2)/2;
    }