4.寻找两个正序数组的中位数

需要重温

class Solution {
    /**
     * 需要重温
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int median = (m + n + 1) / 2;
        int l = -1, r = m + 1;
        while (l < r - 1) {
            int i1 = l + (r - l) / 2; // 有i1个元素在第一个数组
            int i2 = median - i1;
            int ai = (i1 - 1 < 0) ? Integer.MIN_VALUE : nums1[i1 - 1]; // 数组1左侧最大值
            int bi1 = (i2 >= n) ? Integer.MAX_VALUE : nums2[i2];       // 数组2右侧最小值
            if (ai <= bi1) {
                l = i1;
            } else {
                r = i1;
            }
        }

        int i1 = l;
        int i2 = median - i1;
        int ai = (i1 - 1 < 0) ? Integer.MIN_VALUE : nums1[i1 - 1];
        int ai1 = (i1 >= m) ? Integer.MAX_VALUE : nums1[i1];
        int bi = (i2 - 1 < 0) ? Integer.MIN_VALUE : nums2[i2 - 1];
        int bi1 = (i2 >= n) ? Integer.MAX_VALUE : nums2[i2];
        if ((m + n) % 2 == 1) {
            return Math.max(ai, bi);
        } else {
            return (Math.max(ai, bi) + Math.min(ai1, bi1)) / 2.0;
        }

    }
}