【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.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
有两个长度分别为m和n的有序数组nums1和nums2。找到两个排序数组的中位数。总体运行时复杂度应为O（log（m + n））。您可能假设nums1和nums2不能都为空
先说一个数组的中位数怎么求？
如果数组长度为奇数，则直接数组中间的值就是该中位数
如果数组长度为偶数，则把数组从中间等分成两部分，左边数组的最后一个值跟右面数组的第一个值，相加求平均值，就是对应的中位数
如[1,2,3]长度为3，奇数，中间的值是2；[1,2,3,4]长度为偶数，则 （2+3）/2=2.5
到这里，就可以想到，求中位数，只要求到指定位置的数值，即可算出。
也就是，题目变成了求两个有序数组合并后指定位置的值。
为了避免合并数组后的奇数偶数长度判断，统一使用一个算法，可以使用一下方法确认数字位置：
假设 nums1长度m，nums2长度n 那么 （m+n+1）/2 ，和 （m+n+2）/2,这两个位置的值，相加的平均数，就是数组的中间值，不管m+n是奇数还是偶数。
例如
m+n=3,则上面两个位置分别是：2,2,位置是正确的
m+n=4,则上面两个位置分别是：2，3，位置也是正确的
设定要求的位置为K=（m+n+1）/2，数组分别为A，B，要求时间复杂度为O(log(m + n)),则可以使用二分法，递归求解
为了求k位置的值，可以先求出k/2位置的值，此时，两个数组的情况有以下三种情况：
A的长度小于k/2，则B的长度一定大于k/2,因为k的值为（A.length+B.length）/2,因为A的长度已经小于k/2了，必定B的长度大于k/2。
假设 A=[x,y],y>=x
B=[1,2,3,4,5,6,7,8,9,10]
k=(2+10+1)/2=6
k/2=3
则可以将B里k/2长度的[1,2,3]进行剔除，剩余A=[x,y],B=[4,5,6,7,8,9,10],k-k/2=3,重新进行比较
为什么？
无论,x,y在AB合并后的数组里占据什么位置，K永远不可能落在[1,2,3]的范围，例如：
[x,y,1,2,3,4,5,6,7,8,9,10],k的值为4
[1,2,3,x,y,4,5,6,7,8,9,10],k的值为4
[1,2,3,4,5,6,7,8,x,y,9,10],k的值为6·
这样，一次比较，就可以剔除k/2个数据
与情况1的条件相同，只是反过来了，B的长度小于k/2,
假设 B=[x,y],y>=x
A=[1,2,3,4,5,6,7,8,9,10]
k=(2+10+1)/2=6
k/2=3
则可以将A里k/2长度的[1,2,3]进行剔除，剩余B=[x,y],A=[4,5,6,7,8,9,10],k-k/2=3,重新进行比较
既然情况1.2.都不满足了，则说明情况3是A,B长度均大于等于k/2,
例如：
A=[1,3,5]
B=[2,4,6]
k=(3+3+1)/2=3
k/2=1
则同样的，取出A，B，对应位置的值，进行比较，剔除较小的一组
A[1-1]=1,
B[1-1]=2,
1<2,剔除A组[1],剩余A=[3,5],B=[2,4,6],k=3-1=2,继续循环比较