Median of Two Sorted 求两个有序数组的中位数

中位数是把一个数的集合划分为两部分，每部分包含的数字个数相同，并且一个集合中的元素均大于另一个集合中的元素。

因此，我们考虑在一个任意的位置，将数组A划分成两部分。i表示划分数组A的位置，如果数组A包含m个元素，则划分位置有m+1种情况。因此，i的取值范围是0~m。

当i=0时，表示left_A为空；当i=m时，表示right_A为空。

同理，我们也可以划分B数组：

我们把left_A和left_B放到一个集合中，把right_A和right_B放到一个集合中。

如果想要获得中位数，要保证len(left_part)==len(right_part)，并且max(left_part)<=min(right_part)。

因此，我们要寻找i，使其保证：

还要注意i=0,i=m,j=0,j=n的边界条件处理。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> s(nums1);
        vector<int> l(nums2);
        int m=nums1.size();
        int n=nums2.size();
        if(nums1.size()>nums2.size())
        {
            l=nums1;
            s=nums2;
            m=nums2.size();
            n=nums1.size();
        }
        
        int i,j;
        int low=0;
        int high=m;
        int num1,num2;
        while(low<=high)    //这里是对分割位置i进行二分搜索
        {
            i=(low+high)/2;
            j=(m+n+1)/2-i;
            if(i>0 && j<n && s[i-1]>l[j])  //i应当减小
                high=i-1;
            else if(j>0 && i<m && l[j-1]>s[i])  //i应当增大
                low=i+1;
            else
            {
                if(i==0)
                    num1=l[j-1];
                else if(j==0)
                    num1=s[i-1];
                else
                    num1=max(s[i-1],l[j-1]);
                break;
            }
        }
        if((m+n)%2==1)
            return num1;
        if(i==m)
            num2=l[j];
        else if(j==n)
            num2=s[i];
        else
            num2=min(s[i],l[j]);
        return (num1+num2)/2.0;
    }
    
};