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)).
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
Analyze:
array1, len m. cut i, i items on the left, (m-i) on the right.
array2, len n. cut j, j items on the left, (n-j) on the right.
a[0],a[1],...,a[cut-1] | a[cut], a[cut+1], ... a[l-1]
Find cut i in [0,m], and cut j in [0,n] such that
a1[i-1]<=a2[j] && a1[j-1] <= a2[i]
If M+N is even:
i+j = m-i + n-j.
Median = 0.5*(Math.max(a1[i-1], a2[j-1) + Math.min(a1[i], a2[j]));
If M+N is odd:
i+j+1 = m-i + n-j.
Median = Math.min(a1[i], a2[j]);
4. Median of Two Sorted Arrays
原文：http://www.cnblogs.com/neweracoding/p/5616240.html
