Median of Two Sorted Arrays

• leetcode
• Hard
• Company Tags: Google Zenefits Microsoft Apple Yahoo Dropbox Adobe
• Tags: Binary Search Array Divide and Conquer

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

Previous Thinking

The requirement is O(log(m+n)). Obviously, binary search should be used. If we want to find the Kth element in the two arrays.

• if nums1[k/2 - 1] == nums[k/2 - 1], just return the nums1[k/2 - 1].
• if nums1[k/2 - 1] > nums2[k/2 - 1], we can drop the front k/2 elements in the nums2.
• if nums1[k/2 - 1] < nums2[k/2 - 1], we can drop the front k/2 elements in the nums1.

C++ Solution

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int total = m + n;

        if((n + m) % 2 == 0){
            return (findKth(nums1.begin(), nums2.begin(), n, m, total / 2) + findKth(nums1.begin(), nums2.begin(), n, m, total / 2 + 1)) / 2;

        }else{
            return findKth(nums1.begin(), nums2.begin(), n, m, total / 2 + 1);
        }

    }

    double findKth(vector<int>::iterator it1, vector<int>::iterator it2, int n, int m, int k ){
        if(n > m) return findKth(it2,it1,m,n,k);

        if(n == 0) return *(it2 + k - 1);

        if(k == 1) return min(*it2, *it1);

        int ia = min(k / 2, n), ib = k - ia;

        if(*(it1 + ia - 1) < *(it2 + ib - 1)){
            return findKth(it1 + ia, it2, n - ia, m, k - ia);
        }else if(*(it1 + ia - 1) > *(it2 + ib -1)){
            return findKth(it1, it2 + ib, n, m - ib, k -ib);
        }else{
            return *(it1 + ia - 1);
        }
    }
};