Home » C programs » C one-dimensional array programs

C program to find the median of two arrays using a divide and conquer-based efficient solution

Here, we are going to learn how to find the median of two arrays using a divide and conquer-based efficient solution in C programming language?
Submitted by Nidhi, on July 12, 2021

Problem statement

Here, we will create two sorted arrays of the same size. And, we used a divide and conquer-based efficient solution and print the median on the console screen.

Finding median of two arrays using a divide and conquer-based

The source code to find the median of two arrays using a divide and conquer-based efficient solution is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

C program to find median of two arrays using a divide and conquer-based efficient solution

// C program to find the median of two arrays
// using a divide and conquer-based efficient solution

#include <stdio.h>

#define max(a, b) ((a > b) ? a : b)
#define min(a, b) ((a < b) ? a : b)

int median(int arr[], int size)
{
    if (size % 2 == 0)
        return (arr[size / 2] + arr[size / 2 - 1]) / 2;
    else
        return arr[size / 2];
}

int calculateMedian(int arr1[], int arr2[], int size)
{
    if (size <= 0)
        return -1;
    if (size == 1)
        return (arr1[0] + arr2[0]) / 2;
    if (size == 2)
        return (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1])) / 2;

    int m1 = 0;
    int m2 = 0;

    m1 = median(arr1, size);
    m2 = median(arr2, size);

    if (m1 == m2)
        return m1;

    if (m1 < m2) {
        if (size % 2 == 0)
            return calculateMedian(arr1 + size / 2 - 1, arr2, size - size / 2 + 1);

        return calculateMedian(arr1 + size / 2, arr2, size - size / 2);
    }

    if (size % 2 == 0)
        return calculateMedian(arr2 + size / 2 - 1, arr1, size - size / 2 + 1);

    return calculateMedian(arr2 + size / 2, arr1, size - size / 2);
}

int main()
{
    int arr1[] = { 10, 11, 12, 13, 14 };
    int arr2[] = { 21, 22, 23, 24, 25 };

    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    if (size1 != size2) {
        printf("Size of both arrays are different\n");
        return 0;
    }

    printf("Median is: %d\n", calculateMedian(arr1, arr2, size1));

    return 0;
}

Output

Median is: 17

Explanation

In the above program, we created two arrays arr1, arr2 with 5 integer elements. And, we created the calculateMedian() function to calculate the median and return the result to the main() function. After that, we printed the result on the console screen.

C One-Dimensional Array Programs »