Question
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
Solve
设nums1: x1, x2, x3, x4, x5, x6
nums2: y1, y2, y3, y4, y5, y6, y7, y8
所以要找的中位数，即当两数组个数和为奇数时，为中间数；当两数组个数和为偶数，为中间数的平均数。但从找中间数这个思路需要稍微转化一下，应该对两个数组都分别去找一个划分X1、X2和Y1、Y2，使得len(X1)+len(Y1) = len(X2)+len(Y2) = 1/2 * (len(nums1)+len(nums2)) （当然，当总个数为奇数的时候，得不到平均的划分，左边需要多一个）
比如这样划分：
nums1: x1, x2, | x3, x4, x5, x6
nums2: y1, y2, y3, y4, y5, | y6, y7, y8
此时应满足 x2 <= y6 和 y5 <= x3 才是正确的划分，因为此时两数组左边的划分都小于右边的划分，而这正是中位数的定义。
（此题用递归的方法，上面可以看成循环终止条件，下面讨论循环体）
此题要求的时间复杂度是O(log(m+n))，所以很自然地想到用二分查找的方法（通常也会写成递归）。既然要二分，不妨把nums1拿来二分，每次得到nums1的划分，而nums2的划分则通过公式 len(X1)+len(Y1) = len(X2)+len(Y2) = 1/2 * (len(nums1)+len(nums2)) 来确定。（一开始我没有想到这个公式，所以直接对两组数同时进行二分，但很快发现这样两组数的个数会变化）
比如对num1进行二分，
nums1: x1, x2, x3, | x4, x5, x6
nums2: y1, y2, y3, y4, | y5, y6, y7, y8
若x3 >= y5, 则说明num1左边的数过大，应对x1, x2, x3 进行二分；反之，若y4 >= x4, 则说明num1右边的数过大，应对 x4, x5, x6 进行二分。
关键
这题的关键就是只对一组数进行二分，另一组数的划分通过数学的方法推导出来
参考：