有两个升序数组，如何找出这两个数组归并以后新的升序数组的中位数?
中位数把一个升序数组分成了长度相等的两部分，其中左半部分的最大值永远小于或等于右半部分的最小值。
如上图所示，对于偶数长度的数组，可以根据中位数分成长度相等的两部分，左半部分的最大元素（6），永远小于或等于右半部分的最小元素(7)。
如上图所示，对于奇数长度的数组，如果把中位数本身归入左半部分，则左半边长度=右半边长度+1。 左半部分的最大元素（5），永远小于或等于右半部分的最小元素（6）。
假设：
数组A的长度是m，绿色和橙色元素的分界点是i，
数组B的长度是n，绿色和橙色元素的分界点是j，
那么为了让大数组的左右两部分长度相等，则i和j需要符合如下两个条件:
i+j= (m+n+1)/2 (之所以m+n后面+1，是为了应对大数组长度为奇数情况。)
Max(A[i-1],Blj-1])<= Min(A[i], B[j])(就是最大的绿色元素小于或等于最小的橙色元素。)
由于m+n的值是恒定的，所以我们只要确定一个合适的i，就可以确定j，从而找到大数组左半部分和右半部分的分界，也就找到了归并之后大数组的中位数。
其中i可以利用“二分查找”的思想。
如下图所示：
第一步：就如二分查找那样，把i设在数组A的正中位置 i=3:
第二步：根据i的值来确定j的值，j= (m+n+1）/2 -i = 5:
第三步： 验证i和j，分为下面三种情况:
1、B[j-1]≤A[i]&& A[i-1]≤B[j] 说明i和j左侧的元素都小于或等于右侧的元素。
2、A[i]<B[j-1] 说明i对应的元素偏小了，i应该向右侧移动。
3、A[i-1]>B[j] 说明i-1对应的元素偏大了，i应该向左侧移动。
显然，图中的属于情况2，A[3]< B[5]，所以i应该向右移动。
第四步：在数组A的右半部分，重新确定i的位置，就像二分查找一样:
第五步：同第二步，根据i的值来确定j的值，j= (m+n+1）/2-i = 3:
第六步：同第三步，验证i和j: 由于A[5] >=B[2]且B[3]>=A[4]，所以这一组i和j是合适的!
第七步：找出中位数:
如果大数组的长度是奇数，
中位数= Max (A[i-1]，B[j-1]>） (大数组左半部分的最大值。)
如果大数组的长度是偶数，
中位数= (Max (A[i-1]，B[j-1]) +Min（A[i]，B[i]))/2
(大数组左半部分的最大值和大数组右半部分的最小值取平均。)
在图示：大数组的长度是奇数，所以中位数=Max (8，12）=12。
特殊情况：
1、数组A的长度远大于数组B
可以提前把数组A和数组B进行交换，较短的数组放在前面，i从较短的数组中取。由于数组A是较短数组，i的搜索次数减少了。
2、无法找到合适的i值
（1）数组A的长度<数组B的长度，并且数组A的所有元素都>数组B的元素。
可以跳出二分查找的循环，所求的中位数是B[j-1]。（仅限奇数情况)
（2）数组A的长度<数组B的长度，并且数组A的所有元素都<数组B的元素。
可以跳出二分查找的循环，所求的中位数是Max (A[i-1]，B[j-1])。(仅限奇数情况)
def get_middle_number(arrA,arrB):#获取数组的大小m,n=len(arrA),len(arrB)#判断arrA大小>=arrB大小,则交换if m>n:arrA,arrB, m,n,=arrB,arrA,n,m#如果n为0,值异常if n==0:raise ValueError#起点，终点，中间start,end,half=0,m,(m+n+1)//2#循环while start<=end:i=(start+end)//2j=half-i# 验证i和j，三种情况if i<m and arrB[j-1]>arrA[i]:#(1) i偏小了，需要右移start=i+1elif i>0 and arrA[i-1]>arrB[j]:#(2) i偏大了，需要左移end=i-1else:#(3) i刚好合适，或i已达到数组边界if i == 0:max_of_left = arrB[j - 1]elif j == 0:max_of_left = arrA[i - 1]else:max_of_left = max(arrA[i - 1], arrB[j - 1])if (m + n) % 2 == 1:# 如果大数组的长度是奇数，中位数就是左半部分的最大值return max_of_leftif i == m:min_of_right = arrB[j]elif j == n:min_of_right = arrA[i]else:min_of_right = min(arrA[i], arrB[j])# 如果大数组的长度是偶数，取左侧最大值和右侧最小值的平均return (max_of_left + min_of_right) / 2.0if __name__ == '__main__':arrA = list([3, 5, 6, 7, 8, 15, 20])arrB = list([1, 10, 12, 18,21,24,25,29])print(get_middle_number(arrA,arrB))
