Median of two Sorted Arrays of Different Size in C

Last Updated on June 1, 2023 by Mayank Dham

The aim is to determine the median of two sorted arrays, a[] and b[], where N is the number of items in the first array and M is the number of elements in the second array. In this post, we will look at numerous techniques to solve this problem.

Example 1:

Input format: arr1 = [1,4,7,10,12], arr2 = [2,3,6,15]

Output format:

6.00000

Explanation:
Combine the two arrays. The final array is [1,2,3,4,6,7,10,12,15]. We know that the mid element is used to calculate the median. Because the element’s size is unusual. According to the formula, the median will be at the [(n+1)/2]th place in the final sorted array. In this case, the median is at [(9+1)/2]th place, which equals [5]th = 6.

Example 2:

Input: arr1 = [1], arr2 = [2]

Output format:

1.50000

Explanation:
Combine the two arrays. [1,2] is the final sorted array. We know that the mid element is used to calculate the median. Because the element’s size is consistent. The median is defined as the mean of the items in the [n/2]th and [(n/2)+1]th positions of the final sorted array. In this case, the median is (1+2)/2 = 3/2 = 1.50000.

Method 1 : Merging two sorted arrays in a third array

The idea is to merge them into third array and there are two cases:

Case 1: If the length of the third array is odd, then the median is at (length)/2th index in the array obtained after merging both the arrays.

Case 2: If the length of the third array is even, then the median will be the average of elements at index ((length)/2 ) and ((length)/2 – 1) in the array obtained after merging both arrays.

Algorithm to solve merging of two sorted arrays in a third array

1. Merge the two given arrays into one array.
2. Then sort the third(merged) array
3. If the length of the third array is even then:
4. Divide the length of the array by 2. Return (arr[value] + arr[value – 1] / 2).
5. If the length of the third array is odd then:
6. Divide the length of the array by 2 and round that value and return the array[value]

Code implementation in C

#include <stdio.h>
#include <stdlib.h>
int Solution(int arr[], int n)
{
    if (n % 2 == 0)
    {
        int z = n / 2;
        int e = arr[z];
        int q = arr[z - 1];
        int ans = (e + q) / 2;
        return ans;
    }
    else
    {
        int z = n / 2;
        return arr[z];
    }
}

int main()
{
    int arr1[] = {-5, 3, 6, 12, 15};
    int arr2[] = {-12, -10, -6, -3, 4, 10};
    int i = sizeof(arr1) / sizeof(arr1[0]);
    int j = sizeof(arr2) / sizeof(arr2[0]);
    int l = i + j;
    int* arr3 = (int*)malloc(l * sizeof(int));
    for (int k = 0; k < i; k++)
    {
        arr3[k] = arr1[k];
    }

    int a = 0;
    for (int k = i; k < l; k++)
    {
        arr3[k] = arr2[a++];
    }
    for (int m = 0; m < l - 1; m++)
    {
        for (int n = 0; n < l - m - 1; n++)
        {
            if (arr3[n] > arr3[n + 1])
            {
                int temp = arr3[n];
                arr3[n] = arr3[n + 1];
                arr3[n + 1] = temp;
            }
        }
    }
    int median = Solution(arr3, l);
    printf("Median = %d\n", median);
    free(arr3);
    return 0;
}

Output
Median = 4

Method 2 : Merging two sorted arrays using recursion

The idea is simple, calculate the median of both arrays and discard one-half of each array. This approach takes into consideration the size of the arrays. The smaller-sized array is considered the first array in the parameter.

Algorithm to solve merging of two sorted arrays using recursion

1. Create a recursive function that takes two arrays and the sizes of both arrays.
2. Take care of the base cases for the size of arrays less than 2. (previously discussed in Approach).Note: The first array is always the smaller array.
3. Find the middle elements of both arrays. i.e element at (n – 1)/2 and (m – 1)/2 of first and second array respectively. Compare both elements.
4. If the middle element of the smaller array is less than the middle element of the larger array then the first half of the smaller array is bound to lie strictly in the first half of the merged array. It can also be stated that there is an element in the first half of the larger array and the second half of the smaller array which is the median. So, reduce the search space to the first half of the larger array and the second half of the smaller array.
5. Similarly, If the middle element of the smaller array is greater than the middle element of the larger array then reduce the search space to the first half of the smaller array and the second half of the larger array.

Code implementation in C

#include <stdio.h>
float MO2(int a, int b) { return (a + b) / 2.0; }
float MO3(int a, int b, int c)
{
    return a + b + c - ((a > b) ? a : b) - ((a > c) ? a : c) - ((b > c) ? b : c);
}
float MO4(int a, int b, int c, int d)
{
    int max_val = (a > b) ? ((a > c) ? ((a > d) ? a : d) : ((c > d) ? c : d)) : ((b > c) ? ((b > d) ? b : d) : ((c > d) ? c : d));
    int min_val = (a < b) ? ((a < c) ? ((a < d) ? a : d) : ((c < d) ? c : d)) : ((b < c) ? ((b < d) ? b : d) : ((c < d) ? c : d));
    return (a + b + c + d - max_val - min_val) / 2.0;
}
float medianSingle(int arr[], int n)
{
    if (n == 0)
        return -1;
    if (n % 2 == 0)
        return (arr[n / 2] + arr[n / 2 - 1]) / 2.0;
    return arr[n / 2];
}
float findMedianUtil(int A[], int N, int B[], int M)
{
    if (N == 0)
        return medianSingle(B, M);

    if (N == 1)
    {
        if (M == 1)
            return MO2(A[0], B[0]);

        if (M & 1)
            return MO2(B[M / 2], MO3(A[0], B[M / 2 - 1], B[M / 2 + 1]));

        return MO3(B[M / 2], B[M / 2 - 1], A[0]);
    }
    else if (N == 2)
    {
        if (M == 2)
            return MO4(A[0], A[1], B[0], B[1]);

        if (M & 1)
            return MO3(B[M / 2], max(A[0], B[M / 2 - 1]), min(A[1], B[M / 2 + 1]));

        return MO4(B[M / 2], B[M / 2 - 1], max(A[0], B[M / 2 - 2]), min(A[1], B[M / 2 + 1]));
    }

    int idxA = (N - 1) / 2;
    int idxB = (M - 1) / 2;

    if (A[idxA] <= B[idxB])
        return findMedianUtil(A + idxA, N / 2 + 1, B, M - idxA);
    return findMedianUtil(A, N / 2 + 1, B + idxA, M - idxA);
}

float findMedian(int A[], int N, int B[], int M)
{
    if (N > M)
        return findMedianUtil(B, M, A, N);

    return findMedianUtil(A, N, B, M);
}

int main()
{
    int A[] = {900};
    int B[] = {5, 8, 10, 20};
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
    float median = findMedian(A, N, B, M);
    printf("Median = %f\n", median);
    return 0;
}

Output

Median = 10.000000

Method 3 : Merging two sorted arrays using Binary Search

The given two arrays are sorted, so we can utilize the ability of Binary Search to divide the array and find the median. Median means the point at which the whole array is divided into two parts. Hence since the two arrays are not merged so to get the median we require merging which is costly. Hence instead of merging, we will use a modified binary search algorithm to efficiently find the median.

Method 3 : Algorithm to solve merging of two sorted arrays using Binary search

1. If we would have merged the two arrays, the median is the point that will divide the sorted merged array into two equal parts. So the actual median point in the merged array would have been (M+N+1)/2;
2. We divide A[] and B[] into two parts. We will find the mid value and divide the first array A[] into two parts and simultaneously choose only those elements from left of B[] array such that the sum of the count of elements in the left part of both A[] and B[] will result in the left part of the merged array.
3. Now we have 4 variables indicating four values two from array A[] and two from array B[].
4. leftA -> Rightmost element in left part of A.
5. leftb -> Rightmost element in left part of B
6. rightA -> Leftmost element in right part of A
7. rightB -> Leftmost element in right part of B
8. Hence to confirm that the partition was correct we have to check if leftA<=rightB and leftB<=rightA. This is the case when the sum of two parts of A and B results in the left part of the merged array.
9. If the condition fails we have to find another midpoint in A and then left part in B[].
10. If we find leftA > rightB. means we have to decrease the size of A’s partition and shift to lesser value in A[].
11. So update the right pointer of to mid-1 else we will increase the left pointer to mid+1.
12. Repeat the above steps with new partitions till we get the answers.
13. If leftA ≤ rightB and leftB ≤ rightA, then we get the correct partition and our answer depends on the total size of the merged array (i.e. M+N). If (M+N) is even we take max(leftA, leftB) and min(rightA, rightB), add them and divide by 2 to get our answer, else we will just return the maximum of leftA and leftB.

Code implementation in C

#include <stdio.h>
#include <limits.h>

double Median(int A[], int n, int B[], int m)
{
    if (n > m)
        return Median(B, m, A, n); 
    int start = 0;
    int end = n;
    int realmidinmergedarray = (n + m + 1) / 2;

    while (start <= end) {
        int mid = (start + end) / 2;
        int leftAsize = mid;
        int leftBsize = realmidinmergedarray - mid;
        int leftA = (leftAsize > 0) ? A[leftAsize - 1] : INT_MIN; // checking overflow of indices
        int leftB = (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
        int rightA = (leftAsize < n) ? A[leftAsize] : INT_MAX;
        int rightB = (leftBsize < m) ? B[leftBsize] : INT_MAX;

        // if correct partition is done
        if (leftA <= rightB && leftB <= rightA) {
            if ((m + n) % 2 == 0)
                return (double)( (leftA > leftB) ? leftA : leftB ) + ( (rightA < rightB) ? rightA : rightB ) / 2.0;
            return (double)( (leftA > leftB) ? leftA : leftB );
        }
        else if (leftA > rightB) {
            end = mid - 1;
        }
        else {
            start = mid + 1;
        }
    }
    return 0.0;
}
int main()
{
    int arr1[] = { -5, 3, 6, 12, 15 };
    int arr2[] = { -12, -10, -6, -3, 4, 10 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);

    printf("Median of the two arrays is: %.1f\n", Median(arr1, n, arr2, m));

    return 0;
}

Output

Median of the two arrays is: 4.0

Method 4 : Merging two sorted arrays using Priority Queue

In this Approach we have used Priority Queue (min Heap) to find out the median. The Idea is simple Just push the elements into a single Priority Queue from both arrays . Now we have to find median from priority queue by performing a simple traversal through it upto median.

Algorithm to solve merging of two sorted arrays using Priority Queue

1. Start the Median function with the two input vectors A and B.
2. Create a priority queue (min heap) named pq and push all elements from vectors A and B into pq.
3. Calculate the total number of elements (n + m) and store it in the variable check.
4. Initialize variables count and mid1 to -1.
5. Iterate while count is less than check/2.
   Increment count by 1.
   Store the top element from pq in mid1 if count is equal to (check/2)-1.
   Pop the top element from pq.
6. If the total number of elements is odd (check % 2 != 0), return the top element from pq as the median.
7. If the total number of elements is even (check % 2 == 0), calculate the median by taking the average of mid1 and the top element from pq.
8. Return the calculated median.

Code implementation in C

#include <stdio.h>
#include <stdlib.h>
double Median(int A[], int n, int B[], int m)
{
    int i;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (i = 0; i < n; i++)
        pq.push(A[i]);

    for (i = 0; i < m; i++)
        pq.push(B[i]);

    int check = n + m;
    double count = -1;
    double mid1, mid2;

    while (!pq.empty())
    {
        count++;
        if (check % 2 != 0 && count == check / 2)
        {
            double ans = pq.top();
            return ans;
        }
        if (check % 2 == 0 && count == (check / 2) - 1)
            mid1 = pq.top();

        if (check % 2 == 0 && count == check / 2)
        {
            mid2 = pq.top();
            double ans = (mid1 + mid2) / 2;
            return ans;
        }

        pq.pop();
    }

    return 0.0;
}
int main()
{
    int arr1[] = {-2, 3, 4, 5};
    int arr2[] = {-4, -1, 7, 8, 9};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);

    printf("Median of the two arrays are\n");
    printf("%f\n", Median(arr1, n, arr2, m));
    return 0;
}

Output

Median of the two arrays are
4.000000

Conclusion
We have briefly discussed how to find the median of two sorted arrays of different sizes in C with a few examples. Then we have briefly discussed the various methods along with their algorithm, explaining the ways of how to solve this problem.

Frequently Asked Questions (FAQs)

Q1. How can I find the median of two sorted arrays of different sizes in C?
There are multiple approaches to find the median of two sorted arrays in C. One common approach is to merge the arrays into a third array and then find the median based on the size of the merged array. Another approach involves using recursion to divide the arrays and find the median. Additionally, binary search and priority queues can also be used to find the median. The article provides code implementations and explanations for each of these approaches.

Q2.How does the merging of two sorted arrays in a third array help in finding the median?
By merging the two sorted arrays into a third array, you obtain a sorted array containing all the elements from both arrays. This sorted array allows you to easily determine the median. If the length of the merged array is odd, the median is the element at the (length/2)th index. If the length is even, the median is the average of the elements at the (length/2)th and ((length/2) – 1)th indices.

Q3.What is the algorithm for merging two sorted arrays into a third array and finding the median?
The algorithm for merging two sorted arrays into a third array and finding the median involves the following steps:

1. Merge the two arrays into a third array.
2. Sort the third array.
3. If the length of the third array is even, calculate the median as the average of the elements at the (length/2)th and ((length/2) – 1)th indices.
4. If the length of the third array is odd, the median is the element at the (length/2)th index.

Q4.How can I merge two sorted arrays using recursion to find the median?
To merge two sorted arrays using recursion, you can create a recursive function that takes both arrays and their sizes as parameters. The function handles base cases for arrays with sizes less than 2. It then finds the middle elements of both arrays and compares them. Based on the comparison, it recursively divides the arrays into smaller parts until it finds the correct partition. The function considers the size of the arrays and selects the median accordingly.

Q5.How does the binary search approach help in merging two sorted arrays and finding the median?
The binary search approach for merging two sorted arrays and finding the median utilizes the concept of partitioning the arrays. By choosing a mid-point in one array and selecting elements from the other array based on their positions relative to the mid-point, you can efficiently find the correct partition. The binary search technique helps in identifying the correct midpoint and adjusting the partition until the median is found.