题目
给定两个大小别离为 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个数较小的一方，中位数肯定不在它那里。
几个留神点：
- 每轮循环，k缩小的个数，是由被排除的数字个数决定的，而不是间接减半。
查找范畴的边界状况：
如果完结范畴超过了数组范畴，就去数组开端作为完结范畴
如果起始范畴超过了数组范畴，阐明该数组被排空了，间接去另一个数组查看残余的k个数例如有以下两个数组：A: 1 3 4 9B: 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小的数是3B的第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，因而两个正序数组的中位数就是4def 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