题目描述

blablabla

样例

blablabla

二分法

首先为了方便把 短的数组变成nums1
目的：左边一半（nums1的左边i个加上nums2的左边j个）全部小于右边的一半
然后我们二分来找i， i的区间就是[0，nums1.size()]
while loop里面有三种情况：
1. i太大 导致j太小 那么nums2右边第一个 就会比nums1左边最后一个小 所以要把i的上界减小
2. i太小 导致j太大 那么nums1右边第一个 就会比nums2左边最后一个小 所以要把i的下界增加
3. 找到了对的i
找到了对的i之后有2种情况：
1.
m+n是奇数 因为我们算左边一半个数的时候是向上取整的 所以中位数就是左边一半的最大值(maxleft)
如果 i = 0，maxleft就是nums2第j个;
如果 j = 0，maxleft就是nums1第i个；
如果i j 都不是0 maxleft就是nums1第i个和nums2第j个里面大的那个 因为不可能再往更左边取了
2.
m+n是偶数 中位数是左边最大和右边最小(rightmin)的平均数
如果 i = m, rightmin就是nums2第j+1个
如果 j = n, rightmin就是nums1第i+1个
如果i，j都在数组的中间 rightmin就是nums1第i+1个和nums2第j+1个里面小的那个 同理不可能再往更右边取了

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m>n){
            auto temp = nums1;
            nums1 = nums2;
            nums2 = temp;
            swap(m,n);
        }

        // i for nums1, j for nums2 j = (m+n)/2 -i 
        int ileft =0 , iright =m;
        int halflen = (m+n+1)/2;

        while(ileft <= iright){
            int i = (ileft+iright)/2;
            int j = halflen -i;
            // i too large, the min of right part of nums2 less than the max of left part of nums1
            if(i>0 && nums2[j] < nums1[i-1]) iright --;
            // i too small, the min of right aprt of nums1 less than the max of left part of nums2 
            else if(i <m && nums2[j-1] > nums1[i]) ileft ++;
            // i ok
            else{
                int maxleft;
                int rightmin;
                if(i ==0) maxleft = nums2[j-1];
                else if(j ==0) maxleft = nums1[i-1];
                else maxleft = max(nums1[i-1], nums2[j-1]);

                if((m+n)%2 ==1) return maxleft;

                else{
                    if(i ==m) rightmin = nums2[j];
                    else if (j ==n) rightmin = nums1[i];
                    else rightmin = min(nums1[i], nums2[j]);
                }

                return (double)(rightmin+ maxleft)/2;
            }
        }

        return 0;
    }
};