L4 寻找两个有序数组的中位数

搜索 数组

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

解：限制了时间复杂度，中位数定义，奇数为中间那个，偶数为中间连个数字平均。即求(m+n+1)/2和(m+n+2)/2的平均（其中如果M+N为奇数，(m+n+1)/2=(m+n+2)/2）；
在两个数组间使用二分法，要找到总的第K个数字，先在每个数组里找K/2，扔掉一半，直到K缩小到1，选两个数组里较小的那个为第K个数字。

class Solution {
public:
    //返回值double注意/2.0
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size();
        int len2 = nums2.size();
        //special case // len==1 注意位置=长度-1
        // 1,2,3,4
        if(len1 == 0){
            if(len2 >1)
                return  (nums2[(len2+1)/2-1] + nums2[(len2+2)/2-1])/2.0;
            else return nums2[0];
        }
        if(len2 == 0 ){
            if(len1>1)
                return (nums1[(len1+1)/2-1] + nums1[(len1+2)/2-1])/2.0;
            else return nums1[0];
        }
        //find in two array
        // 1,2,3;
        // 3,4,5; 1,2,3,3,4,5;
        int k1 = (len1+len2+1)/2; //3
        int k2 = (len1+len2+2)/2; //4
        return (find(nums1,0,nums2,0,k1)+find(nums1,0,nums2,0,k2))/2.0 ;
    }
    int find(vector<int> nums1,int i,vector<int> nums2, int j, int k){
        // judge in range;
        if(nums1.size() <= i) return nums2[j+k-1];
        if(nums2.size() <= j) return nums1[i+k-1];
        // special case;
        if(k==1) return min(nums1[i],nums2[j]);
        // find k in nums1 from pos i;
        int mid1,mid2;
        if((i+ k/2 -1)<nums1.size()){
            mid1 = nums1[i+ k/2 -1];
        }
        else mid1 = INT_MAX;
        // find k in nums2 from pos j;
        if((j+ k/2 -1)<nums2.size()){
            mid2 = nums2[j+ k/2 -1];
        }
        else mid2 = INT_MAX;
        // compare mid1,mid2
        if(mid1 < mid2) return find(nums1,i+k/2,nums2,j,k-k/2);
        else return find(nums1,i,nums2,j+k/2,k-k/2);
    }
};