Problem description

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

Code

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        int len1 = nums1.size();
        int len2 = nums2.size();
        
        if(len1 == 0) {
            if(len2 % 2 == 1) {
                return nums2[len2 / 2] * 1.0;
            } else {
                int k1 = len2 / 2 + 1;
                int k2 = len2 / 2;
                return (nums2[k1 - 1] + nums2[k2 - 1]) / 2.0;
            }
        } else if(len2 == 0){
            if(len1 % 2 == 1) {
                return nums1[len1 / 2] * 1.0;
            } else {
                int k1 = len1 / 2 + 1;
                int k2 = len1 / 2;
                return (nums1[k1 - 1] + nums1[k2 - 1]) / 2.0;
            }
        }

        if((len1 + len2) % 2 == 1) {
            int k = (len1 + len2) / 2 + 1;
            return find(nums1, nums2, 0, 0, k) * 1.0;
        } else {
            int k1 = (len1 + len2) / 2 + 1;
            int k2 = (len1 + len2) / 2;
            return (find(nums1, nums2, 0, 0, k1) + find(nums1, nums2, 0, 0, k2)) / 2.0;
        }
    }
    
    int find(vector<int> a, vector<int> b, int aStart, int bStart, int k) {
        
        if(aStart > a.size() - 1) {
            return b[bStart + k - 1];
        }
        
        if(bStart > b.size() - 1) {
            return a[aStart + k - 1];
        }
        
        if(k == 1) {
            return a[aStart] < b[bStart] ? a[aStart] : b[bStart];
        }
        
        int aMid = INT_MAX, bMid = INT_MAX;
        
        if(aStart + k / 2 - 1 < a.size()) {
            aMid = a[aStart + k / 2 - 1];
        }
        
        if(bStart + k / 2 - 1 < b.size()) {
            bMid = b[bStart + k / 2 - 1];
        }
        
        if(aMid < bMid) {
            return find(a, b, aStart + k / 2, bStart, k - k / 2);
        } else {
            return find(a, b, aStart, bStart + k / 2, k - k / 2);
        }        
    }
};

Analysis

• 两个数组二分法