给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))。

示例 1:

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.Length;
    int n = nums2.Length;
    if(m>n){
        //保证m<=n
        int[] temp = nums1; nums1 = nums2;nums2 = temp;
        int t = m; m = n; n = t;
    }

    int iMin = 0;
    int iMax = m;//只需要在小的一个数组中寻找i
    int halfLen = (m + n + 1) / 2;//根据公式，用来计算j
    while(iMin <= iMax)
    {
        int i = (iMax + iMin) / 2; //2分法
        int j = halfLen - i; //计算出对应的j
        if(i < iMax && nums2[j-1] > nums1[i])
        {
            iMin = i+1; //数组1的i位置的值小了，数组2的j-1应该小于=数组1的i
        }else if(i > iMin && nums1[i-1] > nums2[j])
        {
            iMax = i-1; //数组1的i位置的值大了，数组1的i-1应该小于=数组2的j
        }else
        {
            //这个位置很合适了，求左边的最大值，注意特殊情况
            int maxLeft = 0;
            if(i == 0){
                maxLeft = nums2[j-1];
            }else if(j == 0)
            {
                maxLeft = nums1[i-1];
            }else{
                maxLeft = Math.Max(nums1[i-1],nums2[j-1]);
            }

            //奇数的话，直接返回左边最大，前面计算i和j会保证左边元素多1
            if((m+n)%2 == 1) return maxLeft;

            //计算右边的最小
            int minRight = 0;
            if(i == m)
            {
                minRight = nums2[j];
            }else if(j == n)
            {
                minRight = nums1[i];
            }else
            {
                minRight = Math.Min(nums2[j],nums1[i]);
            }

            return (maxLeft + minRight)/2f;
        }
    }

    return 0.0;
}

在两个有序的数组中找中位数，中位数是什么，就是可以把一段有序数组分成两段，右边那一段比前面那一段都大。那么就可以想，将有序数组1用i分成两半，同样的将有序数组2用j分成两半，数组1的i和i的右边跟数组2的j和j的右边合并，使他们的个数和左边合并的相同或则少一个，同时合成的右边全都比左边的大，那么在相同个数的情况下，中位数就=（左边最大+右边最小）/2，在左边个数比较多的情况下，中位数就=左边最大。

所以寻找i和j的时候需要保证两个条件，1.左边比右边的个数相同或则多一个。2.数组2第j位大于数组1第i-1位，数组1第i位大于数组2第j-1位，因为i和j是在右边数组，所以一定得保证比它本身上一个元素大。

如果按照这样子区分后，左边最大不是数组1的i-1就是数组2的j-1，而右边最大不是数组1的i就是数组2的j。

时间复杂度是：O(log(min(n,m)))