二分查找O(log(min(m,n)))解决两个有序数组求中位数
题目解析：
这个题目简单来说就是如果将两个已经排序的数组合并为一个虚拟数组，求出这个虚拟数组的中位数即可。
解题思路：
1、这道题最主要的就是切（cut），怎么将数组切成合适的两段是关键，对于一个数组来说在数组的中间将其切成两段，这时候就要分情况讨论，如果是偶数个，中位数就是切点的两边第一个数的平均值，如果是奇数个，中位数就是切点右边的第一个数，比如说1 2 3 4 5，在中间的位置将这个数组切成两段：1 2 \ 3 4 5，很显然，中位数就是3，如果是1 2 3 4，那么就切成了1 2 \ 3 4，很显然中位数就是(2+3)/2 = 2.5。
2、理解了切的思想，接下来就开始在两个数组中进行切，这时候就用到了分治思想。
怎么分？
题目中要求的时间复杂度为 O(log(m + n))，很容易想到的方法就是二分，现在有两个数组，要对那个数组进行二分合适？由于找的是中位数，那么这个数字的两边的元素个数是相等的，所以只需要确定一个数组中的两边元素，两一个数组的对应的补上去就可以了，为了提高效率，要选择最短的数组做二分查找。
怎么治？
这个也很容易，只需要分别比较两个数组切点两边的数就可以，假设数组一中切点两边的元素为L1，R1，数组二中切点两边的元素为：L2，R2，切完之后有三种情况：
1）L1>R2 ，说明数组一的左半边比数组二的右半边大，应该让cut向左移，才能使数组一中较多的数被分配到右边。
2）L2>R1 ，说明数组二的左半边比数组一的右半边大，应该让cut向右移，才能使数组一中较多的数被分配到左边。
3）其他情况（L1<=R2 L2<=R1），cut的位置是正确的，可以停止查找，输出结果。
3.特殊情况
分析完了正常的情况，那么就要分析一下特殊情况；
1)如果有一个数组是空的，直接返回另一个不为空的数组中的中位数
2)如果两个数组元素的个数相等，并且两个数组的中位数相等，直接返回其中一个中位数。
3)有可能在进行二分查找的时候出现了数组越界的情况，只需要定义一个最大值和一个最小值，这样可以按照正常的情况来处理了。
4、输出结果分情况
两个数组的输出情况和之前的一个数组的输出大致是一样，只是添加了选择性，如果是偶数个，输出(min(L1, L2) + min(R1, R2))/2，如果是奇数个，输出min(R1, R2)。
图解思路：
代码解析，时间复杂度为O(log(min(m,n)))
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j-1] > A[i]){
iMin = i + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = i - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }
return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}