两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
你可以假设 A 和 B 不同时为空。
(1)中位数：就是将有序集合分为相等的两部分，并且一边中的元素总是大于另一边
此题的核心思路：就是找到合适的i将nums1分割成两部分（共有m+1种方法），找的合适的j将buns2分割成两部分，使得
len(leftA + leftA) =len(rightA + rughtB);
假设总是m <= n;
则 0 <= i <= m;j=( m + n + 1） / 2 ；B[j - 1] <= A[i]以及A[i-1] <= B[j];
有三种可能
1.i=0或者i=m or B[j -1] <= A[i] 亦或是 j=0或者j=n or A[i -1] <= B[j];意味着i完美，以及完成搜索；
2.j>0 and i 或者i<m B[j−1]>A[i]
这意味着 ii 太小，我们必须增大它。
3.i>0 and j<n A[i−1]>B[j]
这意味着 ii 太大，我们必须减小它。

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        //保证总是m <= n;免得j出现负值
        if (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;//二分查找，从A集合的中间开始判断
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; //i太小需要增加
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i太大需要减小
            }
            else {
                int maxLeft = 0;//左集合中的最大值
                if (i == 0) { maxLeft = B[j-1]; }//A集合为空
                else if (j == 0) { maxLeft = A[i-1]; }//B集合为空
                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]; }//A集合都比B集合小
                else if (j == n) { minRight = A[i]; }//B集合都比A集合小
                else { minRight = Math.min(B[j], A[i]); }//否则取较小值

                return (maxLeft + minRight) / 2.0;//偶数集合则求中间两数的均值
            }
        }
        return 0.0;
    }
}

总之就是中位数分割有序集合为相等两份，不断去找这个分割点儿即可！