题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

参考代码

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

        int Cut1 = 0, Cut2 = 0, LMax1 = 0, LMax2 = 0, RMin1 = 0, RMin2 = 0;
        //数字前后扩充一个位置
        int left = 0, right = 2*n;
        while(left <= right)
        {
            Cut1 = left + (right-left)/2;
            Cut2 = m + n - Cut1;
            //由于扩充了位置除以2才是最终的位置
            LMax1 = Cut1 == 0 ? numeric_limits<int>::min() : nums1[ (Cut1 - 1) / 2];
            RMin1 = Cut1 == 2 * n ? numeric_limits<int>::max() : nums1[ Cut1 / 2];
            LMax2 = Cut2 == 0 ? numeric_limits<int>::min() : nums2[ (Cut2 - 1) / 2];
            RMin2 = Cut2 == 2 * m ? numeric_limits<int>::max() : nums2[ Cut2 / 2];

            if(LMax1 > RMin2)
            {
                right = Cut1 - 1;
            }
            else if(LMax2 > RMin1)
            {
                left = Cut1 + 1;
            }
            else
            {
                break;
            }
        }
        return (max(LMax1, LMax2) + min(RMin1, RMin2))/2.0f;
    }
};