leetcode-go/leetcode/hard/4.median-of-two-sorted-arrays.java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums2.length < nums1.length) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length;
        int k = (m + n + 1) / 2;
        int beg1 = 0, end1 = m;
        while (beg1 <= end1) {
            int i = beg1 + (end1 - beg1) / 2;
            int j = k - i;
            if (0 < i && nums2[j] < nums1[i - 1]) {
                end1 = i - 1; // Take too much
            } else if (i < m && nums1[i] < nums2[j - 1]) {
                beg1 = i + 1; // Take too little
            } else {
                int maxOfLeft = 0, minOfRight = 0;
                if (i == 0) maxOfLeft = nums2[j - 1];
                else if (j == 0) maxOfLeft = nums1[i - 1];
                else maxOfLeft = Math.max(nums1[i-1], nums2[j-1]);
                if (((m + n) & 1) == 1) return (double) maxOfLeft;
                if (i == m) minOfRight = nums2[j];
                else if (j == n) minOfRight = nums1[i];
                else minOfRight = Math.min(nums1[i], nums2[j]);
                return (maxOfLeft + minOfRight) / 2.0;
            }
        }
        return -1.0;
    }
}