Median of 2 Sorted Arrays of Different Sizes

Understanding the Problem

The goal is to find the median of two sorted arrays of different sizes.

Method 1: Simple Merge

This method merges the two arrays and finds the median.

#include <iostream>
using namespace std;

double findMedianSortedArrays(int arr1[], int n1, int arr2[], int n2) {
    int merged[n1 + n2];
    int i = 0, j = 0, k = 0;

    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            merged[k++] = arr1[i++];
        } else {
            merged[k++] = arr2[j++];
        }
    }
    while (i < n1) merged[k++] = arr1[i++];
    while (j < n2) merged[k++] = arr2[j++];

    int total = n1 + n2;
    if (total % 2 == 0) {
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    } else {
        return merged[total / 2];
    }
}

int main() {
    int arr1[] = {1, 3, 8};
    int arr2[] = {7, 9, 10, 11};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Median: " << findMedianSortedArrays(arr1, n1, arr2, n2) << endl;
    return 0;
}
            

Output:

Median: 8.0

Method 2: Binary Search

This method uses binary search to find the median efficiently.

#include <iostream>
#include <climits>
using namespace std;

double findMedianSortedArrays(int arr1[], int n1, int arr2[], int n2) {
    if (n1 > n2) {
        return findMedianSortedArrays(arr2, n2, arr1, n1); // Ensure n1 <= n2
    }

    int low = 0, high = n1;
    while (low <= high) {
        int partition1 = (low + high) / 2;
        int partition2 = (n1 + n2 + 1) / 2 - partition1;

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

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

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((n1 + n2) % 2 == 0) {
                return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
            } else {
                return max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            high = partition1 - 1;
        } else {
            low = partition1 + 1;
        }
    }
    throw invalid_argument("Input arrays are not sorted.");
}

int main() {
    int arr1[] = {1, 3, 8};
    int arr2[] = {7, 9, 10, 11};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << "Median: " << findMedianSortedArrays(arr1, n1, arr2, n2) << endl;
    return 0;
}
            

Output:

Median: 8.0