分治法求解中位数

来先上代码： 

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
           
            if(nums1.size() > nums2.size()){ //如果nums1的长度大于nums2,则交换
                return findMedianSortedArrays(nums2,nums1);
            }

            int len1 = nums1.size();
            int len2 = nums2.size();

            //分割线左边的元素的个数,如果是奇数我们让左边的个数多一个
            int total_left = (len1 + len2 + 1) / 2; //向下取整

            //我们在长度小的那个数组里找分割线,那么长度大的一定含有分割线
            //[0,len1]
            int left  =  0;
            int right =  len1;

            //我们是不是要确定 left 和 right 的位置呀
            //我们在这层循环里只寻妖考虑短的那一边 [0,len1]-->在这里面找分割线
            while(left < right){
                int i = left + (right - left + 1)/2;   //从中间开始-->第一个数组里去的个数
                int j = total_left - i;         //从第二个数组里取的个数

                if(nums1[i - 1] > nums2[j]){
                    right = i - 1;      //那么分割线所在的区间一定为[0,i-1]
                }else{
                    left = i;
                }

            }

            //判断结果
            int i = left;  //-->第一个数组里分割线左边的个数
            int j = total_left - i; //-->第二个数组里分割线左边的个数
            //第一个数组左边最小的和右边最大的
            int nums1LeftMax = i== 0  ? INT_MIN : nums1[i - 1];
            int nums1RightMin = i== len1 ? INT_MAX : nums1[i];
            //第二个数组左边最小的和右边最大的
            int nums2LeftMax = j== 0  ? INT_MIN : nums2[j - 1];
            int nums2RightMin = j== len2 ? INT_MAX : nums2[j];

            if((len1 + len2) % 2 == 0){ //偶数个-->左边最大的和右边最小的和
                int ans1 = max(nums1LeftMax,nums2LeftMax);
                int ans2 = min(nums1RightMin,nums2RightMin);
                return double((ans1 + ans2)/2.0);
            }else{//奇数个-->左边最大大的
                return (double)max(nums1LeftMax,nums2LeftMax);
            }

    }
};