leetcode算法题4：Median of Two Sorted Arrays
算法题目描述：There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty.
1. 算法解决过程
1.1.首先需要了解什么是中位数，中位数用来：
把一个大集合分成两个长度相等的子集，右边的子集总是大于左边的子集 。 如果大集合的长度为偶数，则中位数是中间两个数的平均数，如果长度为奇数，则中位数则是最中间的那一位数字
1.2.利用
折半查找的思想，对两个排序数组进行分割，如A在位置
i处被分割成两段，
由于A有
m个元素，因此分割位置总共有m+1个，（i = 0~m).需要注意，当i=0 时，LeftA为空，当i = m时，RightA为空。分割之后：
len(leftA)= i
len(rightA)=m−i
同理，用相同的方法来分割B，B在
j处被分割为两段，
1.3.顺序数组A和B都被分割之后，将LeftA和和LeftB放在一起，RightA和RightB放在一起，如下图所示;
需要保证如下条件，才能求得中位数：
(1) max(LeftPart)<=min(Right_part), B[j-1]<=A[i] && A[i-1]<= B[j] (2) i + j = （m+n+1）/ 2之所以需要满足条件(2)是因为:
i + j是leftPart的长度，
m+n是集合总长度, 当m+n是偶数时, （m+n+1）/ 2用的是整除（注意python应该用// ),得到的长度是总长度的一半； 当m+n是奇数时,（m+n+1）/ 2用的是整除（注意python应该用// ),得到的长度是总长度的一半再加1;
i + j = （m+n+1）/ 2保证了
LeftPart的长度等于Right_part或者比RightPart多一个。可以得到：
j = （m+n+1）/ 2 - i, 需要注意的是
n>=m, 因为n如果小于m,当i取m时，j可能会变成负数
1.4.开始求中位数：
(1) 当m+n为偶数时， median= （max(leftPart)+min(rightPart)）/ 2 (2)当m+n为奇数时，由于左边的数字个数比右边多一个，所以中位数一定在左边， median= max(leftPart)
2. 具体算法描述
(1) 设imin = 0, imax = m, 在[imin,imax]中进行折半查找 (2) i = （imin + imax)/2, j = (m+n+1)/2 - i (python中注意用//)
(3) 通过(2)可以确定len(LeftPart) = len(RightPart),或者len(LeftPart)= len(RightPart) + 1。然后需要确定:
max(LeftPart)<=min(RightPart) , 即 max(LeftB)<=min(RightA) && max(LeftA)<=ming(RightB)有以下三种情况：
1. B[j-1]<=A[i] && A[i-1]<=B[j], 顺利找到 i , j 的位置停止搜索。
2. B[j-1]>A[i], 此时说明A分割的位置太靠左，需要大一点，因此将 i 向右边移动一步，令imin = i+1, 然后转到（2）
3. A[i-1]>B[j], 此时说明A分割的位置太靠右，需要小一点，因此将 i 向左边移动一步，令imax = i-1, 然后转到（2）
边界问题考虑：
当i = 0时，说明LeftPart没有A的部分，令max(LeftA) = 负无穷；当i = m时，说明RightPart部分没有A的部分，令min(RightA) = 正无穷。
当j = 0时，说明LeftPart没有B的部分，令max(LeftB) = 负无穷；当j = n时，说明RightPart部分没有B的部分，令min(RightB) = 正无穷。
(4) 求出中位数：当m+n为偶数时，median=(max(leftPart)+min(rightPart))/2,
当m+n为奇数时，由于左边的数字个数比右边多一个, 所以中位数一定在左边, median= max(leftPart)
3. python实现代码
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
len_array1 = len(nums1)
len_array2 = len(nums2)
if len_array1 > len_array2:
return self.findMedianSortedArrays(nums2, nums1)
# 要o(log（m+n)的复杂度，所以要折半查找
low = 0
high = len_array1
while low <= high:
array1_portion = (low + high) // 2
array2_portion = (len_array1 + len_array2 + 1) // 2 - array1_portion
# 两个数组分别分成两段之后，分别比较分段点前后数字的大小,需要考虑左边没有或者右边没有的情况
maxLeft_array1 = (array1_portion == 0) and -float('inf') or nums1[array1_portion - 1]
minRight_array1 = (array1_portion == len_array1) and float('inf') or nums1[array1_portion]
maxLeft_array2 = (array2_portion == 0) and -float('inf') or nums2[array2_portion - 1]
minRight_array2 = (array2_portion == len_array2) and float('inf') or nums2[array2_portion]
if maxLeft_array1 <= minRight_array2 and maxLeft_array2 <= minRight_array1:
if (len_array1 + len_array2) % 2 == 0:
median = (max(maxLeft_array2, maxLeft_array1) + min(minRight_array2, minRight_array1)) / 2
return median
else:
median = max(maxLeft_array1, maxLeft_array2)
return median
elif maxLeft_array1 > minRight_array2:
high = array1_portion - 1
else:
low = array1_portion + 1