原文来自：两个排好序数组的中位数
感谢MissMary的思路，这里用中文记录一下：
原题：
有两个排好序的数组nums1和nums2长度分别为m和n，目标是找到这两个数组的中位数，要求运行时间复杂度为O(log(m+n))，假定nums1和nums2不都为空
例子1：
nums1 = [1, 3]
nums2 = [2]
结果为2.0
例子2：
nums1 = [1, 2]
nums2 = [3, 4]
结果为2.5
为了解决这个问题，我们需要知道中位数的特性：中位数将一个排好序的数组分割成两个相同长度的数组，其中一个数组的每一个数字都比另一个数组中的大，如果我们理解了上述这个分割的用法，我们就很容易接近最终答案.
首先，我们先来在一个随机位置 i 处将A数组分割成两半：
因为A有m个元素，所以分割A有m+1个分法(i=0~m)。且我们知道：len(left_A) = i，len(right_A) = m-i.
这里需要注意的是：当i = 0时，left_A是空的，当i = m时，right_A是空的。
用同样的方法，在随机的位置 j 分割B数组：
现在把left_A和left_B放在一个集合中，把right_A和right_B放在另一个集合中，得到：
这样，只要我们保证：
即，左边部分的长度等于右边部分长度，且左边部分的最大值小于右边部分的最小值，这样，我们就可以求得整个数组的中位数：median = (max(left_part) + min(right_part))/2.
为了确保以上两个条件成立，我们只需要保证：
（1）i + j == m - i + n - j + 1
当 n >= m时，我们仅仅设定 i = 0~m，j = (m+n+1)/2 - i
ps:为什么n >= m呢，因为 j 是由 i 通过 j = (m + n + 1)/2 - i（0 <= i <= m）求得，如果n < m，那么 j 可能是负数，这将导致错误的结果。
（2）B[j - 1] <= A[i] 且 A[i - 1] <= B[j]
ps:为了简便讨论，我们先假定A[i - 1], B[j - 1], A[i], B[j]都是有效的，即不考虑边界情况(i = 0/j = n/i = m/j = 0)，这种情况我将留在最后讨论。
所以，我们要做的就是：
在[0, m]中找到这么一个 i ，满足 B[j - 1] <= A[i] 且 A[i - 1] <= B[j] ，其中 j = (m+n+1)/2 - i
我们可以用二分法搜索寻找这个 i ：
<1> 设定 imin = 0，imax = m，然后开始在[ imin, imax ]中搜索 i
<2> 设定 i = ( imin + imax ) / 2, j = ( m + n + 1 ) / 2 - i
<3> 现在，我们可以保证 len(left_part) == len(right_part). 之后会遇到三中情况：
<a> 当B[ j - 1 ] <= A[ i ] 且 A[ i - 1 ] <= B[ j ]时
意味着我们已经找到了这样一个 i ，使得分割的两部分长度相等，且左部分最大值小于有部分最小值
<b> 当B[ j - 1 ] > A[ i ]
因为数组是从小到大排列的，所以意味着 A[ i ]太小，我们必须增大 i 使得 B[ j - 1 ] <= A[ i ]，因为增大 i ，A[ i ]
能够增大，又因为 j = (m + n + 1) / 2 - i，B[ j - 1 ]能够减小
所以，我们必须调整搜索的范围到[ i + 1, imax ]，即设定 imin = i + 1，转到<2>
<c> 当A[ j - 1 ] > B[ i ]
意味A[ i - 1]太大，于是我们必须减小 i 使得 A[ j - 1 ] < B[ i ]， 也就是说，我们必须调整搜索范围到[ imin, i - 1 ]，
即设定 imax = i - 1，转到<2>
至于为什么要用imin， imax方式来折半查找 i ，因为这种算法类似我们玩过的猜数字游戏，比如，一个人要从0到100中选取一个数字，每选取一个数字都会被告知该数字距离目标数字是大了还是小了，这样，为了更快得到最终结果，第一次肯定猜测50，这样可以排除50个数字，若被告知小了，那么下一次猜测肯定猜75，而不是别的数字，只有这样才会更快的猜出目标数字。
好了，现在我们回到这个算法，当我们找到了这个 i ，那么中位数就是：
（1）max(A[ i - 1 ], B[ j - 1 ]) --当 m + n 为奇数时
（2）(max(A[ i - 1 ], B[ j - 1 ]) + min(A[ i ], B[ j ])) / 2 --当 m + n 为偶数时
至于之前讨论过的边界值 i = 0/j = n/i = m/j = 0，会导致A[ j - 1 ], B[ j - 1 ], A[ i ], B[ j ]可能不存在，事实上，这种特殊情况更好理解。
不论如何，我们最终都要确保max(left_part) <= min(right_part)。所以，如果 i 和 j 都不是边界值时（意味着A[ j - 1 ], B[ j - 1 ], A[ i ], B[ j ]都存在），那么我们必须确保 B[ j - 1 ] <= A[ i ] 且 A[ i - 1 ] <= B[ j ]；但是如果A[ j - 1 ], B[ j - 1 ], A[ i ], B[ j ]并不同时存在，那么我们，并不需要上述两个条件都满足。比如，如果 i = 0, j 会等于n，A[ i - 1]不存在，那么我们并不需要满足A[ i - 1 ] <= B[ j ]，也可以获得最终结果，所以我们需要这样更改一下算法：
在[0, m]中找到这么一个 i ，满足 (j == 0 or i == m or B[ j - 1 ] <= A[ i ]) 且 (i == 0 or j == n or A[ i - 1 ] <= B[ j ]) ，其中 j = ( m + n + 1 ) / 2 - i
在三种情况中，应改为：
<a> 当 (j == 0 or i == m or B[ j - 1 ] <= A[ i ]) 且 (i == 0 or j == n or A[ i - 1 ] <= B[ j ])时
意味着 i 就是分割的位置，停止搜索
<b> 当 (i < m and B[ j - 1 ] > A[ i ])
意味着 i 太小了，我们必须提高 i
<c> 当 (i > 0 and A[ i - 1 ] > B[ j ])
意味着 i 太大了，我们必须减小 i
ps: 至于为什么没有判断另一边的临界调节(j == 0 和 j == n)，因为当 i > 0 时，又因为n >= m, j 可以由 i 计算出来，即 j < n，反之当 i < m时, j > 0。
下面是python3代码：
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
m, n = len(nums1), len(nums2)
#promise n>=m, so that j>=0 all time, because j = (m+n+1)/2-i
if(m>n):
nums1, nums2, m, n = nums2, nums1, n, m
imin, imax, half_len = 0, m, (m+n+1)//2
#search i from [0,m]
while imin <= imax:
i = (imin + imax)//2
j = half_len-i
if i<m and nums2[j-1]>nums1[i]:
#i is too small, insrease it
imin = i+1
elif i>0 and nums1[i-1]>nums2[j]:
#i is too big, decrease it
imax = i-1
else:
#i is perfect
if i==0: max_of_left = nums2[j-1]
elif j==0: max_of_left = nums1[i-1]
else: max_of_left = (max(nums1[i-1], nums2[j-1]))
#return derectly when m+n is odd
if(m+n)%2 == 1:
return max_of_left
if i==m: min_of_right = nums2[j]
elif j==n: min_of_right = nums1[i]
else: min_of_right = (min(nums1[i], nums2[j]))
#return when m+n is even
return (min_of_right+max_of_left)/2.0