给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

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

你可以假设 nums1 和 nums2 不会同时为空。

 

示例 1:

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

则中位数是 2.0
示例 2:

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

则中位数是 (2 + 3)/2 = 2.5
思路：
首先题目要求的时间复杂度是O(log(m+n))，所以我们先来个简单暴力的两个有序数组合并，然后在去找中位数。
思路一：暴力解法，时间复杂度O(m+n)
代码如下： 
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m=nums1.length;
            int n=nums2.length;
            int num[]=new int[m+n];
            if(m==0){
                if(n%2==0){
                    return (nums2[n/2-1]+nums2[n/2])/2.0;
                }else {
                    return nums2[n/2];
                }
            }
            if(n==0){
                if(m%2==0){
                    return (nums1[m/2-1]+nums1[m/2])/2.0;
                }else{
                    return nums1[m/2];
                }
            }
            int count=0;
            int i=0;
            int j=0;
            while(count!=(m+n)){
                if(i==m){
                    while(j!=n){
                        num[count++]=nums2[j++];
                    }
                    break;
                }
                if(j==n){
                    while (i!=m){
                        num[count++]=nums1[i++];
                    }
                    break;
                }
                if(nums1[i]<nums2[j]){
                    num[count++]=nums1[i++];
                }else{
                    num[count++]=nums2[j++];
                }
            }
            if(count%2==0){
                return (num[count/2-1]+num[count/2])/2.0;
            }else{
                return num[count/2];
            }
    }
}
思路二：
优化上面的代码，因为两个都是有序数组，而且要求的是中位数，因此我们没必要去归并全部数字，只需要归并一半的数字，假设A数组的长度是m,B数组的长度是n
如果m+n是偶数，那我们只需要求（m+n)/2和（m+n）/2+1位置即可，然后再求平均数，如果是两者相加是奇数，我们直接需要（m+n）/2+1的位置就可。
因此我们需要两个数字一个存着最中间的数字，一个存着他前面的数字，需要一个临时变量，每次循环之前都要将上一次的值赋值给临时变量。
我们仍然需要两个变量表示两个有序数组的开始指针，当A数组的数字小于B数组的时候，我们就要移动A数组，当然需要保证A指针还没超过A数组长度，否则移动B指针，也是需要保证B指针也在长度之内。
代码如下： 
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m=nums1.length;
            int n=nums2.length;
            int s=m+n;
            int right=-1;
            int left=-1;
            int mstart=0;
            int nstart=0;
        for (int i = 0; i <=s/2; i++) {
            left=right;
            if(mstart<m&&(nstart>=n||nums1[mstart]<nums2[nstart])){
                right=nums1[mstart++];
            }else
            {
                right=nums2[nstart++];
            }
        }
        if(s%2==0){
            return (right+left)/2.0;
        }else {
            return right;
        }
    }
}
思路三：
一直到现在我们的时间复杂度还是没有变成O(log(m+n))，思路二虽然优化空间复杂度，利用指针移动记录位置，使得空间复杂度由思路一得O(m+n)变成O(1)。
因为时间复杂度是log所以我们一般会用到二分法。 
class Solution {
   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }
}