题目

给定两个大小别离为 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