Median of Two Sorted Arrays

 You are given two sorted arrays named nums1 and nums2 of length m and n respectively, you have to return the median of these two sorted arrays.

The total run time complexity should not be more than O(log (m+n)).

 

Example 1:

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

Example 2:

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

 

Constraints:

• nums1.size() == m
• nums2.size() == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

Approach :

We will do a binary search in one of the arrays which has a minimum size between the two. 

Firstly, calculate the median position with (n+1)/2. Point two-pointer, say low and high, equal to 0, and the size of the array on which we are applying binary search respectively. Find the partition of the array. 

Check that the left half of the array has an equal element to the current position of the median. If the condition is false, take some elements from the right half (second array ). Now, check if the partitioning is valid. This is only when l1<=r2 and l2<=r1. If valid, return max(l1,l2)(when odd number of elements present) else return (max(l1,l2)+min(r1,r2))/2.

If partitioning is not valid, move ranges. When l1>r2, move left and perform the above operations again. When l2>r2, move right and perform the above operations.

𝐂++ 𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧

class Solution {

public:

    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {

        if(nums2.size()<nums1.size())

            return findMedianSortedArrays(nums2,nums1);

        int n1=nums1.size();

        int n2=nums2.size();

        int low=0,high=n1;

        while(low<=high){

            int cut1=(low+high)>>1;

            int cut2= (n1+n2+1)/2-cut1;

            int l1=cut1==0? INT_MIN : nums1[cut1-1];

            int l2=cut2==0? INT_MIN : nums2[cut2-1];

            int r1=cut1==n1? INT_MAX : nums1[cut1];

            int r2=cut2==n2? INT_MAX : nums2[cut2];

            

            if(l1<=r2 && l2<=r1){

                if((n1+n2)%2==0){

                    return (max(l1,l2)+min(r1,r2))/2.0;

                }

                else

                    return max(l1,l2);

            }

            else if(l1>r2){

                high=cut1-1;

            }

            else{

low=cut1+1;

            }

        }

        return 0.0;

        

    }

};

Success

Details 

Runtime: 71 ms, faster than 43.32% of C++ online submissions for the Median of Two Sorted Arrays.

Memory Usage: 89.3 MB, less than 64.68% of C++ online submissions for Median of Two Sorted Arrays.