There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null) return 0.0;
        if(nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

        // we try to make nums1 shorter

        int m = nums1.length;
        int n = nums2.length;
        int left = 0;
        int right = m;
        while(left < right) {
            int i = left + (right - left)/2;
            int j = (m+n)/2-i;

            int m1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int m2 = i == m ? Integer.MAX_VALUE : nums1[i];
            int n1 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int n2 = j == n ? Integer.MAX_VALUE : nums2[j];

            //System.out.println(i + " " + m1 + " " + m2 + " " + n1 + " " + n2);

            if(m2 >= n1 && n2 >= m1) {
                break;
            } else if( n2 < m1 ) {
                right = i;
            } else {
                left = i + 1;
            }
        }


        int i = left + (right - left)/2;
        int j = (m+n)/2 - i;
        int m1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int m2 = i == m ? Integer.MAX_VALUE : nums1[i];
        int n1 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int n2 = j == n ? Integer.MAX_VALUE : nums2[j];
        //System.out.println(left + " " + m1 + " " + m2 + " " + n1 + " " + n2);
        if((m+n)%2==0) return (double)(Integer.max(m1,n1) + Integer.min(m2, n2)) / 2;
        else return Integer.min(m2, n2);
    } 
}