23.Median of Two Sorted Arrays

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

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.


Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000


Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000


Example 5:
Input: nums1 = [2], nums2 = []
Output: 2.00000

Solution: (Bruteforce)

class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {

        vector<double> v;
        int i = 0;
        int j = 0;
        while (i < nums1.size() && j < nums2.size())
        {
            if (nums1[i] < nums2[j])
            {
                v.push_back(nums1[i]);
                i++;
            }
            else
            {
                v.push_back(nums2[j]);
                j++;
            }
        }

        while (i < nums1.size())
        {
            v.push_back(nums1[i]);
            i++;
        }

        while (j < nums2.size())
        {
            v.push_back(nums2[j]);
            j++;
        }
        if (v.size() % 2 == 0)
        {
            int x = v.size() / 2;
            int y = x - 1;
            
            return (v[x]+v[y]) /2;
        }
        else
        {
            int x = v.size() / 2;
            return v[x];
        }
    }
};

Time Complexity: O(n + m) Space Complexity: O(n + m)

Solution II: (Binary Search)

class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {

        if (nums2.size() < nums1.size())
        {
            return findMedianSortedArrays(nums2, nums1);
        }

        int n = nums1.size();
        int m = nums2.size();

        int start = 0;
        int end = n;

        while (start <= end)
        {

            int partX = (start + end) / 2;
            int partY = (n + m + 1) / 2 - partX;

            double maxLeftX = (partX == 0) ? INT_MIN : nums1[partX - 1];
            double minRightX = (partX == n) ? INT_MAX : nums1[partX];

            double maxLeftY = (partY == 0) ? INT_MIN : nums2[partY - 1];
            double minRightY = (partY == m) ? INT_MAX : nums2[partY];

            if (maxLeftX <= minRightY && maxLeftY <= minRightX)
            {
                if ((n + m) % 2 == 0)
                {
                    return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2;
                }
                else
                {
                    return max(maxLeftX, maxLeftY);
                }
            }
            else if (maxLeftX > minRightY)
            {
                end = partX - 1;
            }
            else
            {
                start = partX + 1;
            }
        }
        return 0;
    }
};

Time Complexity: O(log min(n, m))