[LeetCode] Median of Two Sorted

经典问题

问题
两个有序array的中位数，需要用时O(log (m+n))。

例子
nums1 = [1, 3]，nums2 = [2]，中位数是2。
nums1 = [1, 2]，nums2 = [3, 4]，中位数是(2 + 3)/2 = 2.5。

思路
我们可以把A分成两部分：

          left_A             |        right_A
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

因为A有m个元素，所以这种划分有m+1种：(i = 0∼m)。就是说对于left_A，从一个元素都没有，到包含所有A。len(left_A)=i, len(right_A)=m−i。
同理，B也可以划分成：

          left_B             |        right_B
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

我们把左边归成一边，右边归成一边，同时保证：

1. len(left_part) == len(right_part)
2. max(left_part) <= max(right_part)

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

这样中位数就变成了max(left_part) <= max(right_part)/2。
而那两个条件变成了：

1. i-1+j-1 == m-1-i+n-1-j => 2*(i+j) == (m+n)
2. B[j-1] <= A[i] && A[i-1] <= B[j]

所以我们要做的就是在[0~m]里搜索i，让上面两个条件满足。什么时候搜索停止呢？

1. 设置imin=0, imax=m, 我们在[imin,imax]里面搜索。
2. 设置i=(imin+imax)/2, j=(m+n+1)/2-i。为了j永远为正数，需要n>=m。
3. 在搜索过程中，只会出现三种情况：
   a. B[j-1] <= A[i] && A[i-1] <= B[j]，我们找到了需要的。
   b. B[j-1] > A[i]，说明A[i]太小，我们要增加i。我们把搜索范围调整为[i+1,imax]，也就是imin=i+1。重复2。
   c. B[j-1] < A[i]，说明A[i-1]太大，我们要减小i。我们把搜索范围调整为[imin,i-1]，也就是imax=i-1。重复2。

特殊情况
(j == 0 or i == m or B[j-1] <= A[i]) && (i == 0 or j = n or A[i-1] <= B[j])
说明i很完美，我们可以停止搜索。
中位数会是：
如果(m+n)是奇数，max(A[i-1], B[j-1])，也就是max(left_part)；
如果(m+n)是偶数，(max(A[i-1], B[j-1]) + min(A[i], B[j]))/2，也就是max(left_part) + min(right_part)，其中j=(m+n+1)/2-i。