题目

给定两个大小别离为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的工夫复杂度应该为 O(log (m+n)) 。

输出：nums1 = [1,3], nums2 = [2]
输入：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输出：nums1 = [1,2], nums2 = [3,4]
输入：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

归并排序

利用归并排序的思维，在两个数组结尾，设置两个指针，比拟两个指针的大小，小的向后挪动，直到找到中位数。

这个办法工夫复杂度是O(m+n)，达不到题目的要求，且思考边界状况的代码简单。

二分法

二分法的思维：一个正序数组的中位数，就是该数组第k小的数。例如数组长度是7，中位数就是第4个数。
寻找中位数，转化成寻找第k个数。
将该数组拆成2个正序数组，就是别离在2个数组中寻找第k/2个数。

如果数组a的第k/2个数，小于数组b的第k/2个数，那么数组a中从开始地位到第k/2的地位的这部分数，能够排除掉，中位数肯定不在这些数中
因为，假如中位数在这些数中，最极其的状况就是a的第k/2个数就是中位数，那么数组b的前k/2个数，都应该小于它。
但实际上b的第k/2个数，是大于a的第k/2个数的，所以假如不成立
所以，第k/2个数较小的一方，中位数肯定不在它那里。

几个留神点：

1. 每轮循环，k缩小的个数，是由被排除的数字个数决定的，而不是间接减半。

2. 查找范畴的边界状况：
   如果完结范畴超过了数组范畴，就去数组开端作为完结范畴
   如果起始范畴超过了数组范畴，阐明该数组被排空了，间接去另一个数组查看残余的k个数

   例如有以下两个数组：
   A: 1 3 4 9
   B: 1 2 3 4 5 6 7 8 9
   
   两个有序数组的长度别离是4和9，长度之和是13，
   中位数是整个数组中的第7个元素，因而须要找到第 k=7 小的数。
   
   咱们在两个数组中，先各自找出第3小的数：
   A: 1 3 4 9
       ↑
   B: 1 2 3 4 5 6 7 8 9
       ↑
   A中第3小的数是4，B中第3小的数是3
   B的第3小<A的第3小，能够得出一个论断：
   咱们要找的第7小的数，肯定不在B的前3位当中
   因为，如果第7小的数在B的前3位当中，那么最极其的状况是B中的3就是第7小的数
   第7小的数后面的6个数都不会大于它，B中的3后面有2个数小于3，剩下4个数应该在A中
   然而A中不超过3的数只有2个
   
   所以，咱们要找的第7小的数，肯定不在B的前3位当中，能够把B的前3个数都排除了
   此时，寻找第7小的数，曾经排除了其中的3个，剩下4个
   就在两个数组中，再各自找第2小的数
   A: 1 3 4 9
     ↑
   B: [1 2 3] 4 5 6 7 8 9
             ↑
   A中第2小的数是3，B中第2小的数是5
   同上，第7小的数肯定不在A的前2个数中，排除掉这两个数
   
   寻找第7小的数，后面曾经排除了3个，当初又排除了2个，还剩2个数
   就在两个数组中，再各自找第1小的数
   A: [1 3] 4 9
         ↑
   B: [1 2 3] 4 5 6 7 8 9
           ↑
   A中第1小的数是4，B中第1小的数也是4，相等
   这种状况，咱们当作A<B解决，排除掉A的这1个数，B不动
   
   这是就剩1个数了，此时间接比拟两个数组未排除局部的第1个数，
   较小的那个数就是第7小的数了
   A: [1 3 4] 9
           ↑
   B: [1 2 3] 4 5 6 7 8 9
           ↑
   第7小的数是B中的4，因而两个正序数组的中位数就是4

   def findMedianSortedArrays(nums1, nums2):
    def getTheKNum(k):
        # 两个指针，初始都在0的地位
        start1,start2 = 0,0
        # 开始二分循环排除
        while True:
            # 4. 当start曾经挪动到数组最初+1的地位，阐明该数组以排空，去另一个数组中查看残余的k个数
            if start1==m:
                return nums2[start2+k-1]
            if start2==n:
                return nums1[start1+k-1]
            
            # 5. 当k被排除到只剩1个的时候，此时间接比拟两个数组start地位的数的大小即可，小的那个就是中位数
            if k==1:
                return min(nums1[start1],nums2[start2])
            
            # 1. 依据k值，确定【实践上】两个数组各自要查看几个数
            halfK = k//2
            
            # 2. 确定end的地位: 从start处开始，查看halfk个数，是否会超过数组范畴
            # start是索引，所以start处有start+1个数
            # 从start开始，查看halfk个数，因为蕴含了start地位的数，所以是halfk-1个数
            # 所以从start开始查看halfk个数，共start+1+halfk-1=start+halfk个数
            # 是否超过数组自身的长度范畴 len(nums)，超过了就将end定位到数组开端，没超过就失常
            # end = min(start+halfk,len)-1
            end1 = min(start1+halfK,len(nums1))-1
            end2 = min(start2+halfK,len(nums2))-1
            
            # 3. 确定好要查看几个数后，开始比拟end地位数的大小
            # 小的，排除掉这部分数，从新计算k值，并且挪动start
            if nums1[end1] <= nums2[end2]:
                k = k - (end1-start1+1)
                start1 = end1+1
            else:
                k = k - (end2-start2+1)
                start2 = end2+1
                
    m,n = len(nums1),len(nums2)
    totalLen = m+n
    if totalLen%2 == 1:
        return getTheKNum(totalLen//2+1)
    else:
        return ((getTheKNum(totalLen//2))+(getTheKNum(totalLen//2+1)))/2