# Median of Two Sorted Arrays

Last updated: 29th Aug, 2020

#### Problem Statment

There are two sorted arrays num1 and num2 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 num1 and num2 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

Method - 1:

- Create an array named final_num, that will hold the sorted value (space complexity O(m+n), where m is the size of num1 and n is the size of num2)
- Take two iterator variable i and j to iterate over two arrays num1 and num2 respectively.
- During each iterattions find the lowest value and place that in the array (Worst case Time complexity- O(m+n), Average Case Time Complexity - O(n), Hence the total time complexity is O(n))
- It is possible that one array is of small size and other one is of large size, hence need two more loops.
- Finally find the median.

###### C++ Code

    /// Finding median using normal loop and merge sorted arrays algorithm
    double findMedian(vector<int>& num1,vector<int>& num2)
    {
       vector<int> final_num;
       int i=0,j=0;
       int num1_size = num1.size(),num2_size = num2.size();

       /// Merging the two sorted arrays
       while(i<num1_size && j<num2_size)
       {
           if(num1.at(i) < num2.at(j))
           {
               final_num.push_back(num1.at(i));
               i++;
           }
           else
           {
               final_num.push_back(num2.at(j));
               j++;
           }
       }
       while(j<num2_size)
       {
           final_num.push_back(num2.at(j));
           j++;
       }
       while(i<num1_size)
       {
           final_num.push_back(num1.at(i));
           i++;
       }

       /// Finding the median
       double median;
       int final_size = final_num.size();
       if(final_size%2==0)
       {
           median = (final_num.at(final_size/2) + final_num.at((final_size/2)-1))/2.0;
       }
       else
       {
           median = (final_num.at(final_size/2))*1.0;
       }
       return median;
    }

###### Python Code

    # method to get the median using merge two sorted array algorithm
    def findMedian(self,num1,num2):
        final_num = []
        i = 0
        j = 0
        num1_size = len(num1)
        num2_size = len(num2)

        # merging to sorted arrays
        while(i < num1_size and j < num2_size):
            if(num1[i] < num2[j]):
                final_num.append(num1[i])
                i+=1
            else:
                final_num.append(num2[j])
                j+=1

        while(j < num2_size):
            final_num.append(num2[j])
            j+=1

        while(i < num1_size):
            final_num.append(num1[i])
            i+=1

        # computing the median
        final_size = len(final_num)
        if(final_size%2==0):
            median = (final_num[int(final_size/2)]+final_num[int(final_size/2)-1])/2
        else:
            median = final_num[int(final_size/2)]
        return median

Method - 2:

- Append all the elements of num2 to num1, Space Complexity = O(n), Time complexity = O(n) where n is the size of num2
- sort num1, using the built-in-sort, Time complexity, O(logn) which is less than O(n) in the above point.
- find median using the normal method
- return the median

###### C++ Code

    /// Optimized solution using built-in sort
    double findMedian_optimized(vector<int>& num1,vector<int>& num2)
    {
        double median;
        int num2_size = num2.size();

        /// appending all array elements to one single array
        for(int i=0;i<num2_size;i++)
        {
            num1.push_back(num2.at(i));
        }

        /// sorting the array elements
        sort(num1.begin(),num1.end());
        int num1_size = num1.size();

        /// Finding the median of the array
        if(num1_size%2==0)
        {
            median = (num1.at(num1_size/2-1)+num1.at(num1_size/2))/2.0;
        }
        else
        {
            median = double(num1.at(num1_size/2));
        }
        return median;
    }

###### Python Code

    # method to get the median using an optimized method
    def findMedian_optimized(self,num1,num2):
        num2_size = len(num2)

        # appending both arrays into one
        for i in range(num2_size):
            num1.append(num2[i])

        # sorting the appended array
        num1.sort()

        # computing the median
        final_size = len(num1)

        if(final_size%2==0):
            median = (num1[int(final_size/2)]+num1[int(final_size/2)-1])/2
        else:
            median = num1[int(final_size/2)]
        return float(median)