4. Median of Two Sorted Arrays（圖解）

4. Median of Two Sorted Arrays

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)).

You may assume nums1 and nums2 cannot be both empty.

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

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size())
            return findMedianSortedArrays(nums2,nums1);
        
        int start = 0, end = nums1.size();
        int left1,left2,right1,right2;
        while(start <= end) {
            int mid1 = start + (end - start) / 2;
            int mid2 = (nums1.size() + nums2.size() + 1) / 2 - mid1;
            
            left1 = mid1 != 0 ? nums1[mid1-1] : INT_MIN;
            right1 = mid1 != nums1.size() ? nums1[mid1] : INT_MAX;
            left2 = mid2 != 0 ? nums2[mid2-1] : INT_MIN;
            right2 = mid2 != nums2.size() ? nums2[mid2] : INT_MAX;
            
            if(left1 > right2)
                end = mid1 - 1;
            else if(right1 < left2)
                start = mid1 + 1;
            else
                break;
        }
        if((nums1.size() + nums2.size()) % 2 == 1)
            return max(left1, left2);
        
        return (double)(max(left1, left2) + min(right1, right2)) / 2;
    }
};
           

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        start = 0
        end = len(nums1)
        while start <= end:
            mid1 = start + (end - start) // 2
            mid2 = (len(nums1) + len(nums2) + 1) // 2 - mid1
            
            left1 = nums1[mid1-1] if mid1 != 0 else -float('inf')
            right1 = nums1[mid1] if mid1 != len(nums1) else float('inf')
            left2 = nums2[mid2-1] if mid2 != 0 else -float('inf')
            right2 = nums2[mid2] if mid2 != len(nums2) else float('inf')
            
            if left1 > right2:
                end = mid1 - 1
            elif right1 < left2:
                start = mid1 + 1
            else:
                break
        if (len(nums1) + len(nums2)) % 2 == 1:
            return max(left1, left2)
        else:
            return (max(left1, left2) + min(right1, right2)) / 2
           

Explanation

方法：二分法。對兩個序列較短的那個做二分查找。