寻找中位数

来源：Leetcode第四题寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

先想到了归并两个数组后在从新的有序数组中找中位数，可是这样的时间复杂度是O(m+n)，不符合题目要求。
在查看题解之后知道是要用二分的思想。
简单的说，就是同时对两个数组进行切割，使得数组1左边最大数组2右边最小，数组2左边最大＜数组1右边最小，这样就有中位数是从两个数组左边最大的值和右边最小的值中取出来。 原解答链接：[寻找中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/) C++代码如下： <!--code0--

JAVA

public double find(int[] A,int[] B){
    int len1 = A.length;
    int len2 = B.length;
    if(len1 > len2)
        return find(B,A);
    int iMin = 0 , iMax = len1, mid = (len1 + len2 + 1) / 2;  //对数组划分 mid为两个数组的中间位置
    //imin imax 为 数组A的搜索范围，进而影响到数组B
    while (iMin < iMax){
        int i = (iMax + iMin) / 2;  //数组A的中间值
        int j = mid - i;  //倒推出数组B的中间值
        if(i < iMax && A[i] < B[j-1])  //A的右边最小小了需要扩大搜索范围
            iMin = i + 1;
        else if(i > iMin && B[j] < A[i - 1])  //B的右边最大小了减小搜索范围
            iMax = i - 1;
        else{  //找到期望值
            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((len1 + len2) % 2 == 1)  //数组长度为奇数，直接返回
                return maxLeft;
            int minRight = 0;  //偶数，需要求出右边最小
            if(i == len1)  //特殊情况
                minRight = B[j];
            else if(j == len2)
                minRight = A[i];
            else minRight = Math.min(B[j],A[i]);
            return (minRight + maxLeft) / 2.0;
        }
    }
    return 00.00;
}