# 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);
int n2 = sizeof(arr2) / sizeof(arr2);

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;
}
}

}

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

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

Q1. Can the two sorted arrays have different lengths?

Yes, the two sorted arrays can have different lengths. The algorithms provided in this article can handle arrays of different lengths and find the median efficiently.

Q2. Can the two sorted arrays contain duplicate elements?

Yes, the algorithms provided in this article can handle arrays with duplicate elements. The algorithms merge the arrays while maintaining the sorting order, ensuring accurate calculation of the median.

Q3. What is the space complexity of the median finding algorithms?

The space complexity depends on the specific algorithm used. The algorithms presented in this article have the following space complexities:
Method 1 in C and Python: O(n), where n is the total number of elements in both arrays (due to the merged array).
Method 2 in C: O(1) (constant space) because it does not require an additional merged array.
Also Read: Java Program to Find Whether a Person is Eligible to Vote or Not
Method 2 in Python: O(n), where n is the total number of elements in both arrays (due to the merged array).
Method 1 and 2 in C++: O(n), where n is the total number of elements in both arrays (due to the merged vector).
Also Read: Java Program to Determine the Color of a Chess Square
Method 1 and 2 in Java: O(n), where n is the total number of elements in both arrays (due to the merged priority queues).
It’s important to note that the space complexity does not include the space required to store the input arrays or the output median.

## 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.