Median of two Sorted Arrays of Different Sizes
Last Updated :
02 May, 2024
Given two sorted arrays, a[] and b[], the task is to find the median of these sorted arrays, where N is the number of elements in the first array, and M is the number of elements in the second array.
This is an extension of Median of two sorted arrays of equal size problem. Here we handle arrays of unequal size also.
Examples:
Input: a[] = {-5, 3, 6, 12, 15}, b[] = {-12, -10, -6, -3, 4, 10}
Output: The median is 3.
Explanation: The merged array is: ar3[] = {-12, -10, -6, -5 , -3, 3, 4, 6, 10, 12, 15}.
So the median of the merged array is 3
Input: a[] = {2, 3, 5, 8}, b[] = {10, 12, 14, 16, 18, 20}
Output: The median is 11.
Explanation : The merged array is: ar3[] = {2, 3, 5, 8, 10, 12, 14, 16, 18, 20}
If the number of the elements are even. So there are two middle elements.
Take the average between the two: (10 + 12) / 2 = 11.
Naive Approach to find Median of two sorted Arrays of different sizes
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.
Illustration:
arr1[] = { -5, 3, 6, 12, 15 } , arr2[] = { -12, -10, -6, -3, 4, 10 }
- After merging them in a third array : arr3[] = { -5, 3, 6, 12, 15, -12, -10, -6, -3, 4, 10}
- Sort arr3[ ] = { -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 }
- As the length of arr3 is odd, so the median is 3
Below is the implementation of the above approach:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int Solution(int arr[], int n)
{
// If length of array is even
if (n % 2 == 0) {
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else {
int z = round(n / 2);
return arr[z];
}
}
// Driver Code
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 arr3[i + j];
int l = i + j;
// Merge two array into one array
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++];
}
// Sort the merged array
sort(arr3, arr3 + l);
// calling the method
cout << "Median = " << Solution(arr3, l);
}
// This code is contributed by SoumikMondal
// Java program for the above approach
import java.io.*;
import java.util.Arrays;
public class GFG {
public static int Solution(int[] arr)
{
int n = arr.length;
// If length of array is even
if (n % 2 == 0) {
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else {
int z = Math.round(n / 2);
return arr[z];
}
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
int i = arr1.length;
int j = arr2.length;
int[] arr3 = new int[i + j];
// Merge two array into one array
System.arraycopy(arr1, 0, arr3, 0, i);
System.arraycopy(arr2, 0, arr3, i, j);
// Sort the merged array
Arrays.sort(arr3);
// calling the method
System.out.print("Median = " + Solution(arr3));
}
}
// This code is contributed by Manas Tole
# Python3 program for the above approach
def Solution(arr):
n = len(arr)
# If length of array is even
if n % 2 == 0:
z = n // 2
e = arr[z]
q = arr[z - 1]
ans = (e + q) / 2
return ans
# If length of array is odd
else:
z = n // 2
ans = arr[z]
return ans
# Driver code
if __name__ == "__main__":
arr1 = [-5, 3, 6, 12, 15]
arr2 = [-12, -10, -6, -3, 4, 10]
# Concatenating the two arrays
arr3 = arr1 + arr2
# Sorting the resultant array
arr3.sort()
print("Median = ", Solution(arr3))
# This code is contributed by kush11
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
public static int Solution(int[] arr)
{
int n = arr.Length;
// If length of array is even
if (n % 2 == 0) {
int z = n / 2;
int e = arr[z];
int q = arr[z - 1];
int ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else {
int z = n / 2;
return arr[z];
}
}
// Driver Code
static public void Main()
{
// TODO Auto-generated method stub
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
// Merge two array into one array
var myList = new List<int>();
myList.AddRange(arr1);
myList.AddRange(arr2);
int[] arr3 = myList.ToArray();
// Sort the merged array
Array.Sort(arr3);
// calling the method
Console.Write("Median = " + Solution(arr3));
}
}
// This code is contributed by Shubhamsingh10
// Javascript program for the above approach
function Solution(arr, n)
{
// If length of array is even
if (n % 2 == 0)
{
var z = n / 2;
var e = arr[z];
var q = arr[z - 1];
var ans = (e + q) / 2;
return ans;
}
// If length if array is odd
else
{
var z = Math.floor(n / 2);
return arr[z];
}
}
// Driver Code
// TODO Auto-generated method stub
var arr1 = [ -5, 3, 6, 12, 15 ];
var arr2 = [ -12, -10, -6, -3, 4, 10 ];
var i = arr1.length;
var j = arr2.length;
var l = i+j;
// Merge two array into one array
const arr3 = arr1.concat(arr2);
// Sort the merged array
arr3.sort(function(a, b) {
return a - b;
});
// calling the method
console.log("Median = " + Solution(arr3, l));
// This code is contributed by Shubham Singh
Time Complexity: O((N + M) * Log (N + M)), Time required to sort the array of size N + M
Auxiliary Space: O(N + M), Creating a new array of size N+M.
Median of two sorted arrays of different sizes by Merging Arrays efficiently:
The given arrays are sorted, so merge the sorted arrays in an efficient way and keep the count of elements inserted in the output array or printed form. So when the elements in the output array are half the original size of the given array print the element as a median element. There are two cases:
- Case 1: M+N is odd, the median is at (M+N)/2th index in the array obtained after merging both the arrays.
- Case 2: M+N is even, the median will be the average of elements at index ((M+N)/2 – 1) and (M+N)/2 in the array obtained after merging both the arrays
Illustration:
Given two array ar1[ ]= { 900 } and ar2[ ] = { 5, 8, 10, 20 } , n => Size of ar1 = 1 and m => Size of ar2 = 4
- Loop will run from 0 till 2.
- First iteration : { 900 } { 5, 8, 10, 20 } , m1 = 5
- Second iteration : { 900 } { 5, 8, 10, 20 }, m1 = 8
- Third iteration : { 900 } { 5, 8, 10, 20 }, m1 = 10
- As size of ar1 + ar2 = odd , hence we return m1 = 10 as the median
Below is the implementation of the above approach:
C++
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
#include <bits/stdc++.h>
using namespace std;
/* This function returns median of ar1[] and ar2[].
Assumption in this function:
Both ar1[] and ar2[] are sorted arrays */
int getMedian(int ar1[], int ar2[], int n, int m)
{
int i = 0; /* Current index of input array ar1[] */
int j = 0; /* Current index of input array ar2[] */
int count;
int m1 = -1, m2 = -1;
/*loop till (m+n)/2*/
for (count = 0; count <= (m + n) / 2; count++) {
// store (n+m)/2-1 in m2
m2 = m1;
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,
else {
m1 = ar2[j++];
}
}
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
// other wise median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging ar1 and ar2
if ((m + n) % 2 == 1) {
return m1;
}
else {
return (m1 + m2) / 2;
}
}
/* Driver code */
int main()
{
int ar1[] = { 900 };
int ar2[] = { 5, 8, 10, 20 };
int n1 = sizeof(ar1) / sizeof(ar1[0]);
int n2 = sizeof(ar2) / sizeof(ar2[0]);
cout << getMedian(ar1, ar2, n1, n2);
}
// This is code is contributed by rathbhupendra, modified by
// rajesh999
import java.io.*;
class GFG {
// Function to calculate median
static int getMedian(int ar1[], int ar2[], int n, int m)
{
// Current index of input array ar1[]
int i = 0;
// Current index of input array ar2[]
int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++]
: ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,
else {
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else {
for (count = 0; count <= (n + m) / 2; count++) {
m2 = m1;
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++]
: ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,
else {
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
public static void main(String[] args)
{
int ar1[] = { 900 };
int ar2[] = { 5, 8, 10, 20 };
int n1 = ar1.length;
int n2 = ar2.length;
System.out.println(getMedian(ar1, ar2, n1, n2));
}
}
# A Simple Merge based O(n) solution to find
# median of two sorted arrays
""" This function returns median of ar1[] and ar2[].
Assumption in this function:
Both ar1[] and ar2[] are sorted arrays """
def getMedian(ar1, ar2, n, m):
i = 0 # Current index of input array ar1[]
j = 0 # Current index of input array ar2[]
m1, m2 = -1, -1
for count in range(((n + m) // 2) + 1):
m2 = m1
if(i != n and j != m):
if ar1[i] > ar2[j]:
m1 = ar2[j]
j += 1
else:
m1 = ar1[i]
i += 1
elif(i < n):
m1 = ar1[i]
i += 1
# for case when j<m,
else:
m1 = ar2[j]
j += 1
# return m1 if it's length odd else return (m1+m2)//2
return m1 if (n + m) % 2 == 1 else (m1 + m2) // 2
# Driver code
ar1 = [900]
ar2 = [5, 8, 10, 20]
n1 = len(ar1)
n2 = len(ar2)
print(getMedian(ar1, ar2, n1, n2))
# This code is contributed by isandeep2183 (Sandeep Kumar Sharma)
using System;
class GFG {
// Function to calculate median
static int getMedian(int[] ar1, int[] ar2, int n, int m)
{
// Current index of input array ar1[]
int i = 0;
// Current index of input array ar2[]
int j = 0;
int count;
int m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++]
: ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,
else {
m1 = ar2[j++];
}
}
return m1;
}
// median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else {
for (count = 0; count <= (n + m) / 2; count++) {
m2 = m1;
if (i != n && j != m) {
m1 = (ar1[i] > ar2[j]) ? ar2[j++]
: ar1[i++];
}
else if (i < n) {
m1 = ar1[i++];
}
// for case when j<m,
else {
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
public static void Main(String[] args)
{
int[] ar1 = { 900 };
int[] ar2 = { 5, 8, 10, 20 };
int n1 = ar1.Length;
int n2 = ar2.Length;
Console.WriteLine(getMedian(ar1, ar2, n1, n2));
}
}
//This code is contributed by isandeep2183 ( Sandeep Kumar Sharma )
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
// This function returns median of ar1[] and ar2[].
// Assumption in this function:
// Both ar1[] and ar2[] are sorted arrays
function getMedian(ar1, ar2, n, m)
{
// Current index of input array ar1[]
let i = 0;
// Current index of input array ar2[]
let j = 0;
let count;
let m1 = -1, m2 = -1;
// Since there are (n+m) elements,
// There are following two cases
// if n+m is odd then the middle
// index is median i.e. (m+n)/2
if ((m + n) % 2 == 1)
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// For case when j<m,
else
{
m1 = ar2[j++];
}
}
return m1;
}
// Median will be average of elements
// at index ((m+n)/2 - 1) and (m+n)/2
// in the array obtained after merging
// ar1 and ar2
else
{
for(count = 0;
count <= (n + m) / 2;
count++)
{
m2 = m1;
if (i != n && j != m)
{
m1 = (ar1[i] > ar2[j]) ?
ar2[j++] : ar1[i++];
}
else if(i < n)
{
m1 = ar1[i++];
}
// For case when j<m,
else
{
m1 = ar2[j++];
}
}
return (m1 + m2) / 2;
}
}
// Driver code
let ar1 = [900];
let ar2 = [5, 8, 10, 20];
let n1 = ar1.length;
let n2 = ar2.length;
console.log(getMedian(ar1, ar2, n1, n2));
// This code is contributed by isandeep(Sandeep Kumar Sharma)
Time Complexity: O(M + N). To merge both arrays O(M+N) time is needed.
Auxiliary Space: O(1). No extra space is required.
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.
Below is the implementation:
C++
#include <bits/stdc++.h>
using namespace std;
// Method to find median
double Median(vector<int>& A, vector<int>& B)
{
int n = A.size();
int m = B.size();
if (n > m)
return Median(B, A); // Swapping to make A smaller
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 and leftB <= rightA) {
if ((m + n) % 2 == 0)
return (max(leftA, leftB)
+ min(rightA, rightB))
/ 2.0;
return max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
int main()
{
vector<int> arr1 = { -5, 3, 6, 12, 15 };
vector<int> arr2 = { -12, -10, -6, -3, 4, 10 };
cout << "Median of the two arrays are" << endl;
cout << Median(arr1, arr2);
return 0;
}
public class GFG {
// Method to find median
static double Median(int[] A, int[] B)
{
int n = A.length;
int m = B.length;
if (n > m)
return Median(B,
A); // Swapping to make A smaller
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]
: Integer
.MIN_VALUE; // checking overflow
// of indices
int leftB = (leftBsize > 0) ? B[leftBsize - 1]
: Integer.MIN_VALUE;
int rightA = (leftAsize < n)
? A[leftAsize]
: Integer.MAX_VALUE;
int rightB = (leftBsize < m)
? B[leftBsize]
: Integer.MAX_VALUE;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return (Math.max(leftA, leftB)
+ Math.min(rightA, rightB))
/ 2.0;
return Math.max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
public static void main(String[] args)
{
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
System.out.println("Median of the two arrays are");
System.out.println(Median(arr1, arr2));
}
}
// This code is contributed by Hritik
class Solution:
# Method to find median
def Median(self, A, B):
# Assumption both A and B cannot be empty
n = len(A)
m = len(B)
if (n > m):
return self.Median(B, A) # Swapping to make A smaller
start = 0
end = n
realmidinmergedarray = (n + m + 1) // 2
while (start <= end):
mid = (start + end) // 2
leftAsize = mid
leftBsize = realmidinmergedarray - mid
# checking overflow of indices
leftA = A[leftAsize - 1] if (leftAsize > 0) else float('-inf')
leftB = B[leftBsize - 1] if (leftBsize > 0) else float('-inf')
rightA = A[leftAsize] if (leftAsize < n) else float('inf')
rightB = B[leftBsize] if (leftBsize < m) else float('inf')
# if correct partition is done
if leftA <= rightB and leftB <= rightA:
if ((m + n) % 2 == 0):
return (max(leftA, leftB) + min(rightA, rightB)) / 2.0
return max(leftA, leftB)
elif (leftA > rightB):
end = mid - 1
else:
start = mid + 1
# Driver code
ans = Solution()
arr1 = [-5, 3, 6, 12, 15]
arr2 = [-12, -10, -6, -3, 4, 10]
print("Median of the two arrays is")
print(ans.Median(arr1, arr2))
# This code is contributed by Arpan
using System;
public class GFG {
// Method to find median
static double Median(int[] A, int[] B)
{
int n = A.Length;
int m = B.Length;
if (n > m)
return Median(B,
A); // Swapping to make A smaller
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]
: Int32.MinValue; // checking overflow
// of indices
int leftB = (leftBsize > 0) ? B[leftBsize - 1]
: Int32.MinValue;
int rightA = (leftAsize < n) ? A[leftAsize]
: Int32.MaxValue;
int rightB = (leftBsize < m) ? B[leftBsize]
: Int32.MaxValue;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return (Math.Max(leftA, leftB)
+ Math.Min(rightA, rightB))
/ 2.0;
return Math.Max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
public static void Main()
{
int[] arr1 = { -5, 3, 6, 12, 15 };
int[] arr2 = { -12, -10, -6, -3, 4, 10 };
Console.WriteLine("Median of the two arrays are");
Console.WriteLine(Median(arr1, arr2));
}
}
// This code is contributed by Shubham Singh
<script>
// JavaScript Program to implement
// the above approach
// Method to find median
function Median(A, B) {
let n = A.length;
let m = B.length;
if (n > m)
return Median(B, A); // Swapping to make A smaller
let start = 0;
let end = n;
let realmidinmergedarray = Math.floor((n + m + 1) / 2);
while (start <= end) {
let mid = Math.floor((start + end) / 2);
let leftAsize = mid;
let leftBsize = realmidinmergedarray - mid;
let leftA
= (leftAsize > 0)
? A[leftAsize - 1]
: Number.MIN_VALUE; // checking overflow of indices
let leftB
= (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
let rightA
= (leftAsize < n) ? A[leftAsize] : INT_MAX;
let rightB
= (leftBsize < m) ? B[leftBsize] : INT_MAX;
// if correct partition is done
if (leftA <= rightB && leftB <= rightA) {
if ((m + n) % 2 == 0)
return Math.floor((Math.max(leftA, leftB)
+ Math.min(rightA, rightB))
/ 2.0);
return Math.max(leftA, leftB);
}
else if (leftA > rightB) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
// Driver code
let arr1 = [-5, 3, 6, 12, 15];
let arr2 = [-12, -10, -6, -3, 4, 10];
document.write("Median of the two arrays are" + "<br>");
document.write(Median(arr1, arr2))
// This code is contributed by Potta Lokesh
</script>
OutputMedian of the two arrays are
3
Time Complexity: O(min(log M, log N)): Since binary search is being applied on the smaller of the 2 arrays
Auxiliary Space: O(1)
Median of two sorted arrays of different sizes 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.
Illustration:
A[ ] = {-2, 3, 4, 5}, N = 4 & B[ ] = {-4, -1, 7, 8, 9}, M = 5
Step 1: Adding elements to priority queue(pq) from array A
- pq.push(-2)
- pq.push(3)
- pq.push(4)
- pq.push(5)
After adding array A elements to priority queue it will look as pq = {-2, 3, 4, 5}
Step 2: Adding elements to priority queue(pq) from array B
- pq.push(-4)
- pq.push(-1)
- pq.push(7)
- pq.push(8)
- pq.push(9)
After adding array B elements to priority queue it will look as pq = {-4, -2, -1, 3, 4, 5, 7, 8, 9}
Step 3: Now we have to find median from Priority Queue based on following conditions:
- if N+M is odd
- then traverse priority queue upto (n+m)/2 by popping element by element
- Then display median as pq.top()
- if N+M is even
- then traverse priority queue upto (n+m)/2 && ((n+m)/2)-1
- Then median = average of both top values of priority queue
In this case the median is 4
Below is the implementation of the above problem:
C++
#include <bits/stdc++.h>
using namespace std;
// Method to find median
double Median(vector<int>& A, vector<int>& B)
{
int i;
int n = A.size();
int m = B.size();
// initializing Priority Queue (Min Heap)
priority_queue<int, vector<int>, greater<int> > pq;
// pushing array A values to priority Queue
for (i = 0; i < n; i++)
pq.push(A[i]);
// pushing array B values to priority Queue
for (i = 0; i < m; i++)
pq.push(B[i]);
int check = n + m;
double count = -1;
double mid1, mid2;
while (!pq.empty()) {
count++;
// returning mid value if combined length(n+m) is
// odd
if (check % 2 != 0 && count == check / 2) {
double ans = pq.top();
return ans;
}
// maintaining mid1 value if combined length(n+m) is
// even where we need to maintain both mid values in
// case of even combined length
if (check % 2 == 0 && count == (check / 2) - 1)
mid1 = pq.top();
// now returning the mid2 value with previous
// maintained mid1 value by 2
if (check % 2 == 0 && count == check / 2) {
mid2 = pq.top();
double ans = (mid1 + mid2) / 2;
return ans;
}
pq.pop();
}
return 0.00000;
}
// Driver code
int main()
{
vector<int> arr1 = { -2, 3, 4, 5 };
vector<int> arr2 = { -4, -1, 7, 8, 9 };
cout << "Median of the two arrays are" << endl;
cout << Median(arr1, arr2);
return 0;
}
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;
public class Main {
// Method to find median
public static double Median(Vector<Integer> A,
Vector<Integer> B)
{
int i;
int n = A.size();
int m = B.size();
// initializing Priority Queue (Min Heap)
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>();
// pushing array A values to priority Queue
for (i = 0; i < n; i++) {
pq.add(A.get(i));
}
// pushing array B values to priority Queue
for (i = 0; i < m; i++) {
pq.add(B.get(i));
}
int check = n + m;
double count = -1;
double mid1 = -1, mid2 = -1;
while (!pq.isEmpty()) {
count++;
// returning mid value if combined length(n+m)
// is odd
if (check % 2 != 0 && count == check / 2) {
double ans = pq.peek();
return ans;
}
// maintaining mid1 value if combined
// length(n+m) is even where we need to maintain
// both mid values in case of even combined
// length
if (check % 2 == 0
&& count == (check / 2) - 1) {
mid1 = pq.peek();
}
// now returning the mid2 value with previous
// maintained mid1 value by 2
if (check % 2 == 0 && count == check / 2) {
mid2 = pq.peek();
double ans = (mid1 + mid2) / 2;
return ans;
}
pq.poll();
}
return 0.00000;
}
// Driver code
public static void main(String[] args)
{
Vector<Integer> arr1 = new Vector<Integer>();
arr1.add(-2);
arr1.add(3);
arr1.add(4);
arr1.add(5);
Vector<Integer> arr2 = new Vector<Integer>();
arr2.add(-4);
arr2.add(-1);
arr2.add(7);
arr2.add(8);
arr2.add(9);
System.out.println("Median of the two arrays are");
System.out.println(Median(arr1, arr2));
}
}
# Python code for the above approach
import heapq
def Median(A, B):
n, m = len(A), len(B)
# initializing Priority Queue (Min Heap)
pq = []
# pushing array A values to priority Queue
for i in range(n):
heapq.heappush(pq, A[i])
# pushing array B values to priority Queue
for i in range(m):
heapq.heappush(pq, B[i])
check = n + m
count = -1
mid1, mid2 = -1, -1
while pq:
count += 1
# returning mid value if combined length(n+m) is odd
if check % 2 != 0 and count == check // 2:
return pq[0]
# maintaining mid1 value if combined length(n+m) is even
# where we need to maintain both mid values in case of
# even combined length
if check % 2 == 0 and count == (check // 2) - 1:
mid1 = pq[0]
# now returning the mid2 value with previous maintained
# mid1 value by 2
if check % 2 == 0 and count == check // 2:
mid2 = heapq.heappop(pq)
return (mid1 + mid2) / 2
heapq.heappop(pq)
return 0.00000
# Driver code
arr1 = [-2, 3, 4, 5]
arr2 = [-4, -1, 7, 8, 9]
print("Median of the two arrays are")
print(Median(arr1, arr2))
# This code is contributed by karthik
using System;
using System.Collections.Generic;
namespace MedianOfTwoSortedArrays {
class Program {
static double Median(List<int> A, List<int> B)
{
int n = A.Count;
int m = B.Count;
int i;
// initializing Priority Queue (Min Heap)
var pq = new SortedSet<int>();
// pushing array A values to priority Queue
for (i = 0; i < n; i++)
pq.Add(A[i]);
// pushing array B values to priority Queue
for (i = 0; i < m; i++)
pq.Add(B[i]);
int check = n + m;
double count = -1;
double mid1, mid2;
while (pq.Count != 0) {
count++;
// returning mid value if combined length(n+m)
// is odd
if (check % 2 != 0 && count == check / 2) {
double ans = pq.Min;
return ans;
}
// maintaining mid1 value if combined
// length(n+m) is even where we need to maintain
// both mid values in case of even combined
// length
if (check % 2 == 0
&& count == (check / 2) - 1) {
mid1 = pq.Min;
// now returning the mid2 value with
// previous maintained mid1 value by 2
if (check % 2 == 0 && count == check / 2) {
mid2 = pq.Min;
double ans = (mid1 + mid2) / 2;
return ans;
}
}
pq.Remove(pq.Min);
}
return 0.00000;
}
// Driver Code
static void Main(string[] args)
{
List<int> arr1 = new List<int>{ -2, 3, 4, 5 };
List<int> arr2 = new List<int>{ -4, -1, 7, 8, 9 };
Console.WriteLine("Median of the two arrays are");
Console.WriteLine(Median(arr1, arr2));
Console.ReadLine();
}
}
}
// Method to find median
function Median(A, B) {
let n = A.length;
let m = B.length;
//initializing Priority Queue (Min Heap)
let pq = new PriorityQueue();
//pushing array A values to priority Queue
for (let i = 0; i < n; i++) {
pq.push(A[i]);
}
//pushing array B values to priority Queue
for (let i = 0; i < m; i++) {
pq.push(B[i]);
}
let check = n + m;
let count = -1;
let mid1, mid2;
while (!pq.isEmpty()) {
count++;
//returning mid value if combined length(n+m) is odd
if (check % 2 !== 0 && count === Math.floor(check / 2)) {
let ans = pq.top();
return ans;
}
//maintaining mid1 value if combined length(n+m) is even
//where we need to maintain both mid values in case of even combined length
if (check % 2 === 0 && count === (check / 2) - 1) {
mid1 = pq.top();
}
//now returning the mid2 value with previous maintained mid1 value by 2
if (check % 2 === 0 && count === check / 2) {
mid2 = pq.top();
let ans = (mid1 + mid2) / 2;
return ans;
}
pq.pop();
}
return 0.00000;
}
// Priority Queue (Min Heap) implementation
class PriorityQueue {
constructor() {
this.data = [];
}
push(value) {
this.data.push(value);
this.bubbleUp(this.data.length - 1);
}
pop() {
let result = this.data[0];
let end = this.data.pop();
if (this.data.length > 0) {
this.data[0] = end;
this.bubbleDown(0);
}
return result;
}
top() {
return this.data[0];
}
isEmpty() {
return this.data.length === 0;
}
bubbleUp(index) {
let parent = Math.floor((index + 1) / 2) - 1;
if (parent >= 0 && this.data[parent] > this.data[index]) {
[this.data[parent], this.data[index]] = [this.data[index], this.data[parent]];
this.bubbleUp(parent);
}
}
bubbleDown(index) {
let child1 = (index + 1) * 2 - 1;
let child2 = (index + 1) * 2;
let minIndex = index;
if (child1 < this.data.length && this.data[child1] < this.data[minIndex]) {
minIndex = child1;
}
if (child2 < this.data.length && this.data[child2] < this.data[minIndex]) {
minIndex = child2;
}
if (minIndex !== index) {
[this.data[index], this.data[minIndex]] = [this.data[minIndex], this.data[index]];
this.bubbleDown(minIndex);
}
}
}
// Driver code
let arr1 = [-2, 3, 4, 5];
let arr2 = [-4, -1, 7, 8, 9];
console.log("Median of the two arrays are");
console.log(Median(arr1, arr2));
OutputMedian of the two arrays are
4
Time Complexity: O((n + m) log(n + m)), Since the priority queue is implemented from two arrays
Auxiliary Space: O(N+M): for storing two array values in the priority queue.
Please Login to comment...