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
给出两个有序数组，找出合并后的中位数，给了个限制条件时间在O(log(m + n)),看到log那就肯定是用二分法了。
先扯个远一点的，中位数就是数组中间的那个数，求法和数组长度的奇偶有关，这里介绍个方法可以无视奇偶。核心的原理在于计算机除法的向下取整，6/2=7/2=3。
偶数时：[1,2,3,4,5,6]，midden=(3+4)/2=(arr[2]+arr[3])/2=(arr[n/2-1]+arr[n/2])/2.
n/2-1=(n-2)/2,由于向下取整，4/2=5/2，所以(n-2)/2=(n-1)/2.
于是midden=(arr[(n-1)/2]+arr[n/2])/2；
奇数时:[1,2,3,4,5],midden=3=arr[2]，同样由于向下取整，n=5，n/2=(n-1)/2.
midden=arr[n/2]=arr[(n-1)/2]=(arr[(n-1)/2]+arr[n/2])/2;
综上：无论奇偶，midden=(arr[(n-1)/2]+arr[n/2])/2，记住核心原理，计算机除法的向下取整
回到题目中，我们假设A数组和B数组合二为一（当然不可能在程序中合并，时间限制不允许）
A+B=C,我们假设C是排好序的新数组，现在C可以分为L和R两部分，L中的所有元素R中的
所有元素。L可以分为A1和B1，同样R可以分为A2和B2。因为A1<A2，B1<B2必然成立，因为
A和B是有序数组，所以L<R成立还需要的条件是A1<=B2,B1<=A2。
最后迭代C1和C2来比较，有三种可能
（1）A1>B2说明x需要减小，A1存在过多元素
（2）A2<B1说明x需要增大，A1存在元素过少
（3）A1<=B2,B1<=A2，符合要求，此时midden=（max(A1，B1)+min(A2,B2)）/2
但似乎这只适用于偶数情况下，奇数情况下，例如
[1,3,5,7,9]
[2,4,8,9]并不能得到正确结果，所以还需要我们作进一步处理
下面是这个题解的精髓
A: [1,2,3,4,5]--------->[#,1,#,2,#,3,#,4,#,5,#],长度变为2n+1
B: [1,1,1,1]------------>[#,1,#,1,#,1,#,1,#],长度变为2m+1
借助标记符号#，C总长度为2n+2m+2，这样就变成了偶数个，可以找到一处切割成长度相等的两部分，长度都为m+n+1。在A中C1位置切割，相应的就要在B的C2=m+n-x处切割。
C1=7时，C2=4+5-7=2，切割位置如下
[＃1＃2＃3＃（4/4）＃5＃]
[＃1/1＃1＃1＃]
A1=A2为3，B1=0，B2=1，找出如下关系
A1 = A [（C1-1）/ 2]; A2 = A [C1 / 2];
B1 = B[（C2-1）/ 2]; B2 = B [C2 / 2];
由于允许A1=A2或者B1=B2，人为的把奇偶变成了一种情况
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if (m < n) return findMedianSortedArrays(nums2, nums1);
if (n == 0) return (nums1[(m - 1) / 2] + nums1[m / 2]) / 2.0;
int left = 0, right = 2 * n;
while (left <= right) {
int mid2 = (left + right) / 2;
int mid1 = m + n - mid2;
double L1 = mid1 == 0 ? Double.MIN_VALUE : nums1[(mid1 - 1) / 2];
double L2 = mid2 == 0 ? Double.MIN_VALUE : nums2[(mid2 - 1) / 2];
double R1 = mid1 == m * 2 ? Double.MAX_VALUE : nums1[mid1 / 2];
double R2 = mid2 == n * 2 ? Double.MAX_VALUE : nums2[mid2 / 2];
if (L1 > R2) left = mid2 + 1;
else if (L2 > R1) right = mid2 - 1;
else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2;
}
return -1;
}
}
