Median of Two Sorted Arrays in C, C++, Java and Python

Introduction

Welcome to this comprehensive guide on finding the median of two sorted arrays in C, C++, Java, and Python.

In this article, we will explore various approaches and implementations in these popular programming languages to solve this problem.

Also Read: Longest Substring Without Repeating Characters

The median of two sorted arrays is a commonly encountered problem in algorithmic programming, and having a good understanding of different language-specific techniques will enable you to tackle this problem efficiently.

So, let’s dive in and explore the fascinating world of finding the median of two sorted arrays in C, C++, Java, and Python!

Implementation in C

C is a powerful programming language that offers various approaches to find the median of two sorted arrays efficiently.

In this section, we will discuss two popular methods.

Method 1

One common approach to finding the median of two sorted arrays in C is to use the merge technique. This method involves merging the two arrays into a single sorted array and then finding the median of the merged array.

Also Read: Two Sum in C Programming with Solution: A Comprehensive Guide

Here’s a C implementation of this method:

#include <stdio.h>

float findMedian(int arr1[], int arr2[], int n1, 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;
    int medianIndex = total / 2;

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

int main() {
    int arr1[] = {1, 3, 5};
    int arr2[] = {2, 4, 6, 8};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    float median = findMedian(arr1, arr2, n1, n2);
    printf("Median: %.2f\n", median);

    return 0;
}

This implementation merges the two sorted arrays arr1 and arr2 into the merged array. Then, it calculates the median based on the size of the merged array.

Also Read: Getchar and Putchar in C: A Comprehensive Guide

The time complexity of this method is O(n), where n is the total number of elements in both arrays.

Method 2

Another approach in C involves using the binary search technique to find the median directly without merging the arrays.

This method offers a more optimized solution for finding the median of two sorted arrays.

Here’s a C implementation of this method:

#include <stdio.h>

float findMedian(int arr1[], int n1, int arr2[], int n2) {
    if (n1 > n2) {
        return findMedian(arr2, n2, arr1, n1);
    }

    int low = 0;
    int high = n1;
    int total = n1 + n2;

    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (total + 1) / 2 - partitionX;

        int maxLeftX = (partitionX == 0) ? INT_MIN : arr1[partitionX - 1];
        int minRightX = (partitionX == n1) ? INT_MAX : arr1[partitionX];

        int maxLeftY = (partitionY == 0) ? INT_MIN : arr2[partitionY - 1];
        int minRightY = (partitionY == n2) ? INT_MAX : arr2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if (total % 2 == 0) {
                return (float)(fmax(maxLeftX, maxLeftY) + fmin(minRightX, minRightY)) / 2;
            } else {
                return (float)fmax(maxLeftX, maxLeftY);
            }
        } else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }

    return -1; // Median not found
}

int main() {
    int arr1[] = {1, 3, 5};
    int arr2[] = {2, 4, 6, 8};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    float median = findMedian(arr1, n1, arr2, n2);
    printf("Median: %.2f\n", median);

    return 0;
}

This implementation utilizes the binary search technique to find the partition points in both arrays. It then compares the elements around the partition points to determine the median.

Also Read: C Program to Find the Inverse of 2×2 Matrix

The time complexity of this method is O(log(min(n1, n2))), where n1 and n2 are the lengths of the two arrays.

Implementation in C++

C++ offers powerful features and libraries that simplify the process of finding the median of two sorted arrays. In this section, we will discuss two approaches using C++.

Method 1

One approach in C++ involves merging the arrays and then calculating the median based on the merged array. This approach is similar to Method 1 in the C language.

Here’s a C++ implementation of this approach:

#include <iostream>
#include <vector>

using namespace std;

double findMedian(vector<int>& nums1, vector<int>& nums2) {
    int n1 = nums1.size();
    int n2 = nums2.size();
    vector<int> merged(n1 + n2);

    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2) {
        if (nums1[i] <= nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }

    while (i < n1) {
        merged[k++] = nums1[i++];
    }

    while (j < n2) {
        merged[k++] = nums2[j++];
    }

    int total = n1 + n2;
    int medianIndex = total / 2;

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

int main() {
    vector<int> nums1 = {1, 3, 5};
    vector<int> nums2 = {2, 4, 6, 8};

    double median = findMedian(nums1, nums2);
    cout << "Median: " << median << endl;

    return 0;
}

This implementation uses vectors to store the input arrays and the merged array. It then calculates the median based on the size of the merged array.

Also Read: Length of String C++: Tips and Tricks for Effective Programming

The time complexity of this approach is O(n), where n is the total number of elements in both arrays.

Approach 2

Another approach in C++ utilizes the std::merge function from the <algorithm> library to merge the arrays. This approach offers a more concise and efficient solution.

Here’s a C++ implementation of this approach:

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

using namespace std;

double findMedian(vector<int>& nums1, vector<int>& nums2) {
    int n1 = nums1.size();
    int n2 = nums2.size();
    vector<int> merged(n1 + n2);

    merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), merged.begin());

    int total = n1 + n2;
    int medianIndex = total / 2;

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

int main() {
    vector<int> nums1 = {1, 3, 5};
    vector<int> nums2 = {2, 4, 6, 8};

    double median = findMedian(nums1, nums2);
    cout << "Median: " << median << endl;

    return 0;
}

This implementation utilizes the std::merge function to merge the input arrays into the merged vector. Then, it calculates the median based on the size of the merged vector.

Also Read: Reverse a String in C++: A Comprehensive Guide

The time complexity of this approach is O(n log n), where n is the total number of elements in both arrays.

Implementation in Java

Java provides a rich set of libraries and features that make it convenient to find the median of two sorted arrays. In this section, we will explore two solutions using Java.

Method 1

One approach in Java involves merging the arrays and then calculating the median based on the merged array. This approach is similar to Method 1 in the C language.

Also Read: Factorial of a Number using Command Line Arguments in Java

Here’s a Java implementation of this approach:

public class MedianOfTwoSortedArrays {
    public static double findMedian(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[] merged = new int[n1 + n2];

        int i = 0, j = 0, k = 0;
        while (i < n1 && j < n2) {
            if (nums1[i] <= nums2[j]) {
                merged[k++] = nums1[i++];
            } else {
                merged[k++] = nums2[j++];
            }
        }

        while (i < n1) {
            merged[k++] = nums1[i++];
        }

        while (j < n2) {
            merged[k++] = nums2[j++];
        }

        int total = n1 + n2;
        int medianIndex = total / 2;

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

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5};
        int[] nums2 = {2, 4, 6, 8};

        double median = findMedian(nums1, nums2);
        System.out.println("Median: " + median);
    }
}

This implementation creates a new array merged to store the merged values of nums1 and nums2. Then, it calculates the median based on the size of the merged array.

The time complexity of this approach is O(n), where n is the total number of elements in both arrays.

Method 2

Another approach in Java involves using the PriorityQueue class to efficiently merge and find the median of the two arrays.

Also Read: Java Program to Determine the Color of a Chess Square

Here’s a Java implementation of this approach:

import java.util.PriorityQueue;

public class MedianOfTwoSortedArrays {
    public static double findMedian(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int total = n1 + n2;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        for (int num : nums1) {
            maxHeap.offer(num);
        }

        for (int num : nums2) {
            maxHeap.offer(num);
        }

        while (maxHeap.size() - minHeap.size() > 1) {
            minHeap.offer(maxHeap.poll());
        }

        if (total % 2 == 0) {
            minHeap.offer(maxHeap.poll());
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5};
        int[] nums2 = {2, 4, 6, 8};

        double median = findMedian(nums1, nums2);
        System.out.println("Median: " + median);
    }
}

This implementation uses two PriorityQueue objects, minHeap and maxHeap, to efficiently merge the two arrays and find the median.

The minHeap stores the larger half of the merged values, while the maxHeap stores the smaller half. The time complexity of this approach is O(n log n), where n is the total number of elements in both arrays.

Python

Python provides an elegant and concise syntax that simplifies the process of finding the median of two sorted arrays.

Also Read: Python Array Slice: A Comprehensive Guide to Slicing Arrays

In this section, we will explore two algorithms using Python.

Method 1

One algorithm in Python involves merging the arrays and then calculating the median based on the merged array. This algorithm is similar to Method 1 in the C language.

Here’s a Python implementation of this algorithm:

def findMedian(nums1, nums2):
    merged = sorted(nums1 + nums2)
    total = len(merged)
    median_index = total // 2

    if total % 2 == 0:
        return (merged[median_index - 1] + merged[median_index]) / 2
    else:
        return merged[median_index]

nums1 = [1, 3, 5]
nums2 = [2, 4, 6, 8]

median = findMedian(nums1, nums2)
print("Median:", median)

This implementation uses the sorted function to merge the nums1 and nums2 arrays and create the merged array.

Then, it calculates the median based on the size of the merged array. The time complexity of this algorithm is O(n log n), where n is the total number of elements in both arrays.

Also Read: Numpy ndarray Object is not Callable: Understanding the Issue

Method 2

Another algorithm in Python involves utilizing the heapq module to merge and find the median of the two arrays efficiently.

Here’s a Python implementation of this algorithm:

import heapq

def findMedian(nums1, nums2):
    merged = []
    heapq.merge(nums1, nums2, merged)
    total = len(merged)
    median_index = total // 2

    if total % 2 == 0:
        return (merged[median_index - 1] + merged[median_index]) / 2
    else:
        return merged[median_index]

nums1 = [1, 3, 5]
nums2 = [2, 4, 6, 8]

median = findMedian(nums1, nums2)
print("Median:", median)

This implementation uses the heapq.merge function to merge the nums1 and nums2 arrays into the merged array.

Then, it calculates the median based on the size of the merged array. The time complexity of this algorithm is O(n log n), where n is the total number of elements in both arrays.

Also Read: Numpy Repeat: An In-depth Guide to Repeating Elements

FAQs

Conclusion

In this article, we explored various algorithms and implementations for finding the median of two sorted arrays in C, C++, Java, and Python. We discussed different approaches and provided code examples for each language.

We started by understanding the concept of the median and its significance in statistics. Then, we delved into the problem of finding the median of two sorted arrays and discussed multiple solutions.

In C, we explored two methods: one involving merging the arrays and another using a divide-and-conquer approach. Both methods provided efficient ways to calculate the median, depending on the specific requirements of the application.

In C++, we discussed two approaches. The first approach utilized the std::merge function to merge the arrays, while the second approach involved using vectors and the STL nth_element function. Both approaches offered effective ways to find the median.

Moving on to Java, we presented two solutions. The first solution merged the arrays and calculated the median based on the merged array, while the second solution utilized PriorityQueue to efficiently merge and find the median.

Lastly, in Python, we explored two algorithms. The first algorithm merged the arrays using the sorted function, and the second algorithm utilized the heapq module for efficient merging and median calculation.

Throughout the article, we provided detailed code examples and explanations for each implementation. We discussed the time and space complexities of the algorithms and addressed frequently asked questions related to the problem.

In conclusion, finding the median of two sorted arrays is a common problem in programming and data analysis. The solutions provided in this article offer efficient and reliable ways to calculate the median in C, C++, Java, and Python.