Searching: Find median of two sorted array of different sizes

Problem Statement:

You are given 2 sorted arrays of different sizes, you need to find the median.

If the total elements in combined array is odd, then finding middle element is easy.

If the total elements in combined array is even, then take the 2 middle elements and then take the average of the two.

Example:

Input: a = [-2, -1, 1, 2, 3] b = [5, 6, 7, 8]
Output: 3

Merged array = [-2, -1, 1, 2, 3, 5, 6, 7, 8 ]

Solution 1: Bruteforce approach

In this approach, combine both the arrays and then sort the array.

Based on the size of the new array is even or odd, find the middle element and return the result.

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

Solution 2: Binary search

We can also use binary search to solve the problem.

WE can partition the two arrays into to two halves, in such a way that the elements in the left half are less than or equal to the element of right half.

By doing so, we can see that the median lies in boundary of the two halves.

Time Complexity: O(logm/logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

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

    vector<int> merged;
    for (int i = 0; i < n; i++) 
    {
        merged.push_back(nums1[i]);
    }

    for (int i = 0; i < m; i++) 
    {
        merged.push_back(nums2[i]);
    }

    sort(merged.begin(), merged.end());

    int total = merged.size();

    if (total % 2 == 1) 
    {

        return (merged[total / 2]);
    } 
    else 
    {

        int middle1 = merged[total / 2 - 1];
        int middle2 = merged[total / 2];

        return (middle1 + middle2) / 2.0;
    }
}

double solution_2(vector<int>& nums1, vector<int>& nums2) 
{
    int m = nums1.size();
    int n = nums2.size();

    if (m > n) 
    {
        swap(nums1, nums2);
        swap(m, n);
    }

    int left = 0;
    int right = m;
    int mid = (m + n + 1) / 2; 

    while (left <= right) 
    {
        int partition1 = left + (right - left) / 2;
        int partition2 = mid - partition1;

        int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
        int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];

        int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
        int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) 
        {
            if ((m + n) % 2 == 0) 
            {
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
            } 
            else 
            {
                return max(maxLeft1, maxLeft2);
            }
        } 
        else if (maxLeft1 > minRight2) 
        {
            right = partition1;
        } 
        else 
        {
            left = partition1 + 1;
        }
    }

    return 0.0; 
}

int main() 
{
    vector<int> a = { 1, 2, 3, 4, 5 };
    vector<int> b = { 6, 7, 8, 9, 10 };

    cout << solution_1(a, b) << endl;
    cout << solution_2(a, b) << endl;
    return 0;
}

Output

5.5
5.5