Problem Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Solution

The O(log (m+n)) time complexity reminds us the binary search. The keypoint is that two arrays are sorted, and the position mid of a median is known if given a merged sorted array. Therefore, there's still one degree of freedom. Suppose mid1 is the index in the array nums1 where all elements with positions less than mid1 are smaller(equal) than the median, then we immediately know all elements in the array nums2 with positions less than mid2=mid-mid1 are also smaller(equal) than the median. Thus, the problem is to find such an appropriate mid1. At the same time, elements with indices larger than mid1 in nums1 should be larger than the median, and similarly for elements in nums2.

And be sure to consider all corner cases, indices are within the bounds and the +1/-1 issue.

Java Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        if(len1 > len2) return findMedianSortedArrays(nums2, nums1);
        // now len1 <= len2
        int len = len1 + len2, avg1 = (len-1)/2, avg2 = len/2;
        if(len1 == 0) return (nums2[avg1] + nums2[avg2])/2.0;
        int l = 0, r = len1, p1 = (l+r)/2, p2 = avg2 - p1 - 1; 
        while( l<r ){
            p1 = (l+r)/2;
            p2 = avg2 - p1 - 1;
            if( p2+1<len2 && nums1[p1] > nums2[p2+1] ){
                r = p1;
            }else if( p1+1<len1 && nums2[p2] > nums1[p1+1] ){
                l = p1 + 1;
            }else{
                if(len%2 == 1) return Math.max(nums1[p1], nums2[p2]);
                if(p1-1>=0 && nums1[p1-1]>nums2[p2]) return (nums1[p1-1] + nums1[p1])/2.0;
                if(p2-1>=0 && nums2[p2-1]>nums1[p1]) return (nums2[p2-1] + nums2[p2])/2.0;
                return (nums1[p1] + nums2[p2])/2.0;
            }
        }
        // l>=r is possible when l=0, r=1 => l=0, r=0, which means nums1 has only one element, and is larger than the median
        return (nums2[avg1] + nums2[avg2])/2.0;
    }
}