输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if(m > n) {
            return findMedianSortedArrays(nums2, nums1); // 保证nums1是最短的
        }
        
		// 指定nums1数组的左右区间，不需要指定nums2，因为下面可以通过公式得到对应的划分位置
        int left = 0, right = m; // 这里right=m是为了进入循环，但其实本质是right=m-1才对
        while(left <= right) {
            int i = left + (right - left) / 2; // 要获取靠右边的位置
            int j = (m + n + 1) / 2 - i;
 
            // 拿到划分位置左右两个值，若不存在则用最大和最小值代替
            int ALeft = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int ARight = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int BLeft = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int BRight = (j == n) ? Integer.MAX_VALUE : nums2[j];
 
            if(ALeft <= BRight && BLeft <= ARight) {
                if((m + n) % 2 == 0) {
                    return (Math.max(ALeft, BLeft) + Math.min(ARight, BRight)) / 2.0;
                } else {
                    return Math.max(ALeft, BLeft);
                }
            } else if(ALeft > BRight) {
                right = i - 1;
            } else {
                left  = i + 1;
            }
        }
        return 0.0;
    }
}