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)).

1刷
把题目从find median转换为find k/2 th最小值。注意边界条件当k = 1时取A[0]与B[0]两数中较小者。
Time Complexity O(log(m + n)，Space Complexity O(1)

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       int len = nums1.length + nums2.length;
       if(len%2 == 0){
           return (findKth(nums1, 0, nums2, 0, len/2) + 
                findKth(nums1, 0, nums2, 0, len/2 + 1))/2.0;
       }
       else return findKth(nums1, 0, nums2, 0, len/2 + 1);
    }
    
    private double findKth(int[] A, int A_start, int[] B, int B_start, int k){
        if(A_start >= A.length){
            return B[B_start + k - 1];
        }
        if(B_start >= B.length){
            return A[A_start + k - 1];
        }
        if(k == 1) return Math.min(A[A_start], B[B_start]);
        int A_key = A_start + k/2 - 1 < A.length? A[A_start + k/2 - 1]:Integer.MAX_VALUE;
        int B_key = B_start + k/2 - 1 < B.length? B[B_start + k/2 - 1]:Integer.MAX_VALUE;
        if(A_key < B_key)
            return findKth(A, A_start+k/2, B, B_start, k-k/2);
        else return findKth(A, A_start, B, B_start+k/2, k-k/2);
    }
}

二刷
居然完全忘记了要怎么做。

我们要找到这样的i, j
(1) i + j == m - i + n - j (or: m - i + n - j + 1)
if n >= m, we just need to set: i = 0 ~ m, j = (m + n + 1)/2 - i
(2) B[j-1] <= A[i] and A[i-1] <= B[j]
那么i, j所在的地方即是中位数（一半的元素）。

initial: imin = 0, imax = m, i = (imin + imax)/2, j = (m+n+1)/2 - i. 此时满足len(left_part) == len(right_part)

• B[j-1] <= A[i] and A[i-1] <= B[j] 我们找到了i, 结束search
• B[j-1] > A[i], 我们需要调整i。增大i, 减小j. 设置imin = i+1, 重新进入该循环
• A[i-1] > B[j]，设置imax = i-1, 重新进入该循环
  最终推出循环时 output=
• if m+n是奇数，max(A[i-1], B[j-1])
• if m+n是偶数， (max(A[i-1], B[j-1]) + min(A[i], B[j]))/2

public class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if(m>n) return findMedianSortedArrays(B, A);
        if(m == 0){
            if(n%2 == 0) return (B[n/2-1] + B[n/2])/2.0;
            else return B[n/2];
        }
         int minidx = 0, maxidx = m, i = 0, j = 0, num1 = 0, mid = (m + n + 1) >> 1, num2 = 0;
        while (minidx <= maxidx)
        {
            i = (minidx + maxidx) >> 1;
            j = mid - i;
            if (i<m && j>0 && B[j-1] > A[i]) minidx = i + 1;
            else if (i>0 && j<n && B[j] < A[i-1]) maxidx = i - 1;
            else
            {
              if (i == 0) num1 = B[j-1];
              else if (j == 0) num1 = A[i - 1];
              else num1 = Math.max(A[i-1],B[j-1]);
              break;
            }
          }
          if (((m + n) % 2 == 1)) return num1;
          if (i == m) num2 = B[j];
          else if (j == n) num2 = A[i];
          else num2 = Math.min(A[i],B[j]);
          return (num1 + num2) / 2.;
    }
}