Median of two Sorted Arrays of Different Sizes

Given two sorted arrays, a[] and b[], the task is to find the median of these sorted arrays. Assume that the two sorted arrays are merged and then median is selected from the combined 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: 3
Explanation: The merged array is [-12, -10, -6, -5 , -3, 3, 4, 6, 10, 12, 15]. So the median of the merged array is 3.

Input: a[] = [1, 12, 15, 26, 38], b[] = [2, 13, 17, 30, 45, 60]
Output: The median is 17.
Explanation : The merged array is [1, 2, 12, 13, 15, 17, 26, 30, 38, 45, 60]. So the median of the merged array is 17.

Input: a[] = [], b[] = [2, 4, 5, 6]
Output: The median is 4.5
Explanation: The merged array is [2, 4, 5, 6]. The total number of elements are even, so there are two middle elements. Take the average between the two: (4 + 5) / 2 = 4.5

[Naive Approach] Using Sorting - O((n + m) * log (n + m)) Time and O(n + m) Space

The idea is to concatenate both the arrays into a new array, sort the new array and return the middle of the new sorted array.

Illustration:

a[] = [ -5, 3, 6, 12, 15 ], b[] = [ -12, -10, -6, -3, 4, 10 ]

• After concatenating them in a third array: c[] = [ -5, 3, 6, 12, 15, -12, -10, -6, -3, 4, 10]
• Sort c[] = [ -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 ]
• As the length of c[] is odd, so the median is the middle element = 3

// C++ Code to find Median of two Sorted Arrays of  // Different Sizes using Sorting #include <iostream> #include <vector> #include <algorithm> using namespace std; double medianOf2(vector<int>& a, vector<int>& b) {    // Merge both the arrays  vector<int> c(a.begin(), a.end());  c.insert(c.end(), b.begin(), b.end());  // Sort the concatenated array  sort(c.begin(), c.end());    int len = c.size();    // If length of array is even  if (len % 2 == 0)   return (c[len / 2] + c[len / 2 - 1]) / 2.0;    // If length of array is odd  else   return c[len / 2]; } int main() {  vector<int> a = { -5, 3, 6, 12, 15 };  vector<int> b = { -12, -10, -6, -3, 4, 10 };  cout << medianOf2(a, b) << endl;  return 0; } 

// C Code to find Median of two Sorted Arrays of  // Different Sizes using Sorting #include <stdio.h> // Function to compare two integers for qsort int compare(const void *a, const void *b) {  return (*(int*)a - *(int*)b); } double medianOf2(int a[], int n, int b[], int m) {    // Calculate the total size of the concatenated array  int len = n + m;    int c[len];    // Concatenate a and b into c  for (int i = 0; i < n; ++i)  c[i] = a[i];  for (int i = 0; i < m; ++i)  c[n + i] = b[i];    // Sort the concatenated array  qsort(c, len, sizeof(int), compare);    // Calculate and return the median  int mid = len / 2;    // If length of array is even  if (len % 2 == 0)   return (c[mid] + c[mid - 1]) / 2.0;    // If length of array is odd  else   return c[mid]; } int main() {  int a[] = { -5, 3, 6, 12, 15 };  int b[] = { -12, -10, -6, -3, 4, 10 };    int n = sizeof(a) / sizeof(a[0]);  int m = sizeof(b) / sizeof(b[0]);    printf("%f\n", medianOf2(a, n, b, m));    return 0; } 

// Java Code to find Median of two Sorted Arrays of  // Different Sizes using Sorting import java.util.*; class GfG {  static double medianOf2(int[] a, int[] b) {  // Merge both the arrays  int[] c = new int[a.length + b.length];  System.arraycopy(a, 0, c, 0, a.length);  System.arraycopy(b, 0, c, a.length, b.length);  // Sort the concatenated array  Arrays.sort(c);  int len = c.length;  // If length of array is even  if (len % 2 == 0)  return (c[len / 2] + c[len / 2 - 1]) / 2.0;  // If length of array is odd  else  return c[len / 2];  }  public static void main(String[] args) {  int[] a = { -5, 3, 6, 12, 15 };  int[] b = { -12, -10, -6, -3, 4, 10 };  System.out.println(medianOf2(a, b));  } } 

# Python Code to find Median of two Sorted Arrays of  # Different Sizes using Sorting def medianOf2(a, b): # Merge both the arrays c = a + b # Sort the concatenated array c.sort() len_c = len(c) # If length of array is even if len_c % 2 == 0: return (c[len_c // 2] + c[len_c // 2 - 1]) / 2.0 # If length of array is odd else: return c[len_c // 2] if __name__ == "__main__": a = [-5, 3, 6, 12, 15] b = [-12, -10, -6, -3, 4, 10] print(medianOf2(a, b)) 

// C# Code to find Median of two Sorted Arrays of  // Different Sizes using Sorting using System; using System.Linq; class GfG {  static double MedianOf2(int[] a, int[] b) {    // Merge both the arrays  int[] c = a.Concat(b).ToArray();  // Sort the concatenated array  Array.Sort(c);    int len = c.Length;    // If length of array is even  if (len % 2 == 0)   return (c[len / 2] + c[len / 2 - 1]) / 2.0;    // If length of array is odd  else   return c[len / 2];  }  static void Main() {  int[] a = { -5, 3, 6, 12, 15 };  int[] b = { -12, -10, -6, -3, 4, 10 };  Console.WriteLine(MedianOf2(a, b));  } } 

// JavaScript Code to find Median of two Sorted Arrays of  // Different Sizes using Sorting function medianOf2(a, b) {  // Merge both the arrays  let c = [...a, ...b];  // Sort the concatenated array  c.sort((x, y) => x - y);  let len = c.length;  // If length of array is even  if (len % 2 === 0)   return (c[len / 2] + c[len / 2 - 1]) / 2.0;  // If length of array is odd  else   return c[Math.floor(len / 2)]; } // Driver Code let a = [-5, 3, 6, 12, 15]; let b = [-12, -10, -6, -3, 4, 10]; console.log(medianOf2(a, b)); 

3 

Time Complexity: O((n + m)*log (n + m)), as we are sorting the merged array of size n + m.
Auxiliary Space: O(n + m), for storing the merged array.

[Better Approach] Use Merge of Merge Sort - O(m + n) Time and O(1) Space

The given arrays are sorted, so merge the sorted arrays in an efficient way and keep the count of elements merged so far. So when we reach half of the total, print the median. There can be two cases: 

• Case 1: m+n is odd, the median is the ((m+n)/2)^th element while merging the arrays.
• Case 2: m+n is even, the median will be the average of ((m+n)/2 - 1)^th and ((m+n)/2)^th element while merging the arrays.

// C++ Code to find the median of two sorted arrays // using Merge of Merge Sort #include <iostream> #include <vector> using namespace std; double medianOf2(vector<int>& a, vector<int>& b) {  int n = a.size(), m = b.size();  int i = 0, j = 0;    // m1 to store the middle element  // m2 to store the second middle element  int m1 = -1, m2 = -1;  // Loop till (m+n)/2  for (int count = 0; count <= (m + n) / 2; count++) {  m2 = m1;    // If both the arrays have remaining elements  if (i != n && j != m)  m1 = (a[i] > b[j]) ? b[j++] : a[i++];    // If only a[] has remaining elements  else if (i < n)   m1 = a[i++];    // If only b[] has remaining elements  else   m1 = b[j++];  }  // Return median based on odd/even size  if ((m + n) % 2 == 1)   return m1;  else  return (m1 + m2) / 2.0; } int main() {  vector<int> arr1 = { -5, 3, 6, 12, 15};  vector<int> arr2 = { -12, -10, -6, -3, 4, 10 };  cout << medianOf2(arr1, arr2) << endl;  return 0; } 

// C Code to find the median of two sorted arrays // using Merge of Merge Sort #include <stdio.h> double medianOf2(int a[], int n, int b[], int m) {  int i = 0, j = 0;    // m1 to store the middle element  // m2 to store the second middle element  int m1 = -1, m2 = -1;  // Loop till (m+n)/2  for (int count = 0; count <= (m + n) / 2; count++) {  m2 = m1;    // If both the arrays have remaining elements  if (i != n && j != m)  m1 = (a[i] > b[j]) ? b[j++] : a[i++];    // If only a[] has remaining elements  else if (i < n)   m1 = a[i++];    // If only b[] has remaining elements  else   m1 = b[j++];  }  // Return median based on odd/even size  if ((m + n) % 2 == 1)   return m1;  else  return (m1 + m2) / 2.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("%f\n", medianOf2(arr1, n, arr2, m));  return 0; } 

// Java Code to find the median of two sorted arrays // using Merge of Merge Sort import java.util.*; class GfG {  static double medianOf2(int[] a, int[] b) {  int n = a.length, m = b.length;  int i = 0, j = 0;    // m1 to store the middle element  // m2 to store the second middle element  int m1 = -1, m2 = -1;  // Loop till (m + n)/2  for (int count = 0; count <= (m + n) / 2; count++) {  m2 = m1;    // If both the arrays have remaining elements  if (i != n && j != m)  m1 = (a[i] > b[j]) ? b[j++] : a[i++];    // If only a[] has remaining elements  else if (i < n)   m1 = a[i++];    // If only b[] has remaining elements  else   m1 = b[j++];  }  // Return median based on odd/even size  if ((m + n) % 2 == 1)   return m1;  else  return (m1 + m2) / 2.0;  }  public static void main(String[] args) {  int[] arr1 = { -5, 3, 6, 12, 15 };  int[] arr2 = { -12, -10, -6, -3, 4, 10 };  System.out.println(medianOf2(arr1, arr2));  } } 

# Python Code to find the median of two sorted arrays # using Merge of Merge Sort def medianOf2(a, b): n = len(a) m = len(b) i = 0 j = 0 # m1 to store the middle element # m2 to store the second middle element m1 = -1 m2 = -1 # Loop till (m+n)/2 for count in range((m + n) // 2 + 1): m2 = m1 # If both the arrays have remaining elements if i != n and j != m: if a[i] > b[j]: m1 = b[j] j += 1 else: m1 = a[i] i += 1 # If only a[] has remaining elements elif i < n: m1 = a[i] i += 1 # If only b[] has remaining elements else: m1 = b[j] j += 1 # Return median based on odd/even size if (m + n) % 2 == 1: return m1 else: return (m1 + m2) / 2.0 if __name__ == "__main__": arr1 = [-5, 3, 6, 12, 15] arr2 = [-12, -10, -6, -3, 4, 10] print(medianOf2(arr1, arr2)) 

// C# Code to find the median of two sorted arrays // using Merge of Merge Sort using System; class GfG {  static double medianOf2(int[] a, int[] b) {  int n = a.Length, m = b.Length;  int i = 0, j = 0;  // m1 to store the middle element  // m2 to store the second middle element  int m1 = -1, m2 = -1;  // Loop till (m+n)/2  for (int count = 0; count <= (m + n) / 2; count++) {  m2 = m1;  // If both the arrays have remaining elements  if (i != n && j != m)  m1 = (a[i] > b[j]) ? b[j++] : a[i++];  // If only a[] has remaining elements  else if (i < n)  m1 = a[i++];  // If only b[] has remaining elements  else  m1 = b[j++];  }  // Return median based on odd/even size  if ((m + n) % 2 == 1)  return m1;  else  return (m1 + m2) / 2.0;  }  static void Main() {  int[] arr1 = { -5, 3, 6, 12, 15 };  int[] arr2 = { -12, -10, -6, -3, 4, 10 };  Console.WriteLine(medianOf2(arr1, arr2));  } } 

// JavaScript Code to find the median of two sorted arrays // using Merge of Merge Sort function medianOf2(a, b) {  let n = a.length, m = b.length;  let i = 0, j = 0;  // m1 to store the middle element  // m2 to store the second middle element  let m1 = -1, m2 = -1;  // Loop till (m+n)/2  for (let count = 0; count <= (m + n) / 2; count++) {  m2 = m1;  // If both the arrays have remaining elements  if (i != n && j != m)  m1 = (a[i] > b[j]) ? b[j++] : a[i++];  // If only a[] has remaining elements  else if (i < n)   m1 = a[i++];  // If only b[] has remaining elements  else   m1 = b[j++];  }  // Return median based on odd/even size  if ((m + n) % 2 === 1)   return m1;  else  return (m1 + m2) / 2.0; } // Driver Code let arr1 = [-5, 3, 6, 12, 15]; let arr2 = [-12, -10, -6, -3, 4, 10]; console.log(medianOf2(arr1, arr2)); 

3 

Time Complexity: O(n + m), where n and m are lengths of a[] and b[] respectively.
Auxiliary Space: O(1), No extra space is required.

[Expected Approach] Using Binary Search - O(log(min(n, m)) Time and O(1) Space

Prerequisite: Median of two sorted arrays of same size

The approach is similar to the Binary Search approach of Median of two sorted arrays of same size with the only difference that here we apply binary search on the smaller array instead of a[].

• Consider the first array is smaller. If first array is greater, then swap the arrays to make sure that the first array is smaller.
• We mainly maintain two sets in this algorithm by doing binary search in the smaller array. Let mid1 be the partition of the smaller array. The first set contains elements from 0 to (mid1 - 1) from smaller array and mid2 = ((n + m + 1) / 2 - mid1) elements from the greater array to make sure that the first set has exactly (n+m+1)/2 elements. The second set contains remaining half elements.
• Our target is to find a point in both arrays such that all elements in the first set are smaller than all elements in the elements in the other set (set that contains elements from right side). For this we validate the partitions using the same way as we did in Median of two sorted arrays of same size.

Why do we apply Binary Search on the smaller array?

Applying Binary Search on the smaller array helps us in two ways:

• Since we are applying binary search on the smaller array, we have optimized the time complexity of the algorithm from O(logn) to O(log(min(n, m)).
• Also, if we don't apply the binary search on the smaller array, then then we need to set low = max(0, (n + m + 1)/2 - m) and high = min(n, (n + m + 1)/2) to avoid partitioning mid1 or mid2 outside a[] or b[] respectively.

To avoid handling such cases, we can simply binary search on the smaller array.

// C++ Program to find the median of two sorted arrays // of different size using Binary Search #include <iostream> #include <vector> #include <limits.h> using namespace std; double medianOf2(vector<int> &a, vector<int> &b) {  int n = a.size(), m = b.size();   // If a[] has more elements, then call medianOf2   // with reversed parameters  if (n > m)  return medianOf2(b, a);    int lo = 0, hi = n;  while (lo <= hi) {  int mid1 = (lo + hi) / 2;  int mid2 = (n + m + 1) / 2 - mid1;  // Find elements to the left and right of partition in a[]  int l1 = (mid1 == 0 ? INT_MIN : a[mid1 - 1]);  int r1 = (mid1 == n ? INT_MAX : a[mid1]);  // Find elements to the left and right of partition in b[]  int l2 = (mid2 == 0 ? INT_MIN : b[mid2 - 1]);  int r2 = (mid2 == m ? INT_MAX : b[mid2]);  // If it is a valid partition  if (l1 <= r2 && l2 <= r1) {    // If the total elements are even, then median is   // the average of two middle elements  if ((n + m) % 2 == 0)  return (max(l1, l2) + min(r1, r2)) / 2.0;    // If the total elements are odd, then median is   // the middle element  else  return max(l1, l2);  }  // Check if we need to take lesser elements from a[]  if (l1 > r2)  hi = mid1 - 1;    // Check if we need to take more elements from a[]  else  lo = mid1 + 1;  }  return 0; } int main() {  vector<int> a = {1, 12, 15, 26, 38};  vector<int> b = {2, 13, 17, 30, 45, 60};    cout << medianOf2(a, b);  return 0; } 

// C Program to find the median of two sorted arrays // of different size using Binary Search #include <stdio.h> #include <limits.h> double medianOf2(int a[], int n, int b[], int m) {  // If a[] has more elements, then call medianOf2  // with reversed parameters  if (n > m)  return medianOf2(b, m, a, n);  int lo = 0, hi = n;  while (lo <= hi) {  int mid1 = (lo + hi) / 2;  int mid2 = (n + m + 1) / 2 - mid1;  // Find elements to the left and right of partition in a[]  int l1 = (mid1 == 0) ? INT_MIN : a[mid1 - 1];  int r1 = (mid1 == n) ? INT_MAX : a[mid1];  // Find elements to the left and right of partition in b[]  int l2 = (mid2 == 0) ? INT_MIN : b[mid2 - 1];  int r2 = (mid2 == m) ? INT_MAX : b[mid2];  // If it is a valid partition  if (l1 <= r2 && l2 <= r1) {    // If the total elements are even, then median is   // the average of two middle elements  if ((n + m) % 2 == 0)  return (max(l1, l2) + min(r1, r2)) / 2.0;  // If the total elements are odd, then median is   // the middle element  else  return max(l1, l2);  }  // Check if we need to take fewer elements from a[]  if (l1 > r2)  hi = mid1 - 1;  // Check if we need to take more elements from a[]  else  lo = mid1 + 1;  }  return 0; } // Helper functions for max and min int max(int a, int b) {  return a > b ? a : b; } int min(int a, int b) {  return a < b ? a : b; } int main() {  int a[] = {1, 12, 15, 26, 38};  int b[] = {2, 13, 17, 30, 45, 60};    int n = sizeof(a) / sizeof(a[0]);  int m = sizeof(b) / sizeof(b[0]);  printf("%f\n", medianOf2(a, n, b, m));  return 0; } 

// Java Program to find the median of two sorted arrays // of different size using Binary Search import java.util.*; class GfG {  static double medianOf2(int[] a, int[] b) {  int n = a.length, m = b.length;  // If a[] has more elements, then call medianOf2 with reversed parameters  if (n > m)  return medianOf2(b, a);  int lo = 0, hi = n;  while (lo <= hi) {  int mid1 = (lo + hi) / 2;  int mid2 = (n + m + 1) / 2 - mid1;  // Find elements to the left and right of partition in a[]  int l1 = (mid1 == 0) ? Integer.MIN_VALUE : a[mid1 - 1];  int r1 = (mid1 == n) ? Integer.MAX_VALUE : a[mid1];  // Find elements to the left and right of partition in b[]  int l2 = (mid2 == 0) ? Integer.MIN_VALUE : b[mid2 - 1];  int r2 = (mid2 == m) ? Integer.MAX_VALUE : b[mid2];  // If it is a valid partition  if (l1 <= r2 && l2 <= r1) {  // If the total elements are even, then median is   // the average of two middle elements  if ((n + m) % 2 == 0)  return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;  // If the total elements are odd, then median is   // the middle element  else  return Math.max(l1, l2);  }  // Check if we need to take fewer elements from a[]  if (l1 > r2)  hi = mid1 - 1;  // Check if we need to take more elements from a[]  else  lo = mid1 + 1;  }  return 0;  }  public static void main(String[] args) {  int[] a = {1, 12, 15, 26, 38};  int[] b = {2, 13, 17, 30, 45, 60};  System.out.println(medianOf2(a, b));  } } 

# Python Program to find the median of two sorted arrays # of different size using Binary Search def medianOf2(a, b): n = len(a) m = len(b) # If a[] has more elements, then call medianOf2  # with reversed parameters if n > m: return medianOf2(b, a) lo = 0 hi = n while lo <= hi: mid1 = (lo + hi) // 2 mid2 = (n + m + 1) // 2 - mid1 # Find elements to the left and right of partition in a[] l1 = (mid1 == 0) and float('-inf') or a[mid1 - 1] r1 = (mid1 == n) and float('inf') or a[mid1] # Find elements to the left and right of partition in b[] l2 = (mid2 == 0) and float('-inf') or b[mid2 - 1] r2 = (mid2 == m) and float('inf') or b[mid2] # If it is a valid partition if l1 <= r2 and l2 <= r1: # If the total elements are even, then median is  # the average of two middle elements if (n + m) % 2 == 0: return (max(l1, l2) + min(r1, r2)) / 2.0 # If the total elements are odd, then median is  # the middle element else: return max(l1, l2) # Check if we need to take lesser elements from a[] if l1 > r2: hi = mid1 - 1 # Check if we need to take more elements from a[] else: lo = mid1 + 1 return 0 if __name__ == "__main__": a = [1, 12, 15, 26, 38] b = [2, 13, 17, 30, 45, 60] print(medianOf2(a, b)) 

// C# Program to find the median of two sorted arrays // of different size using Binary Search using System; class GfG {  static double medianOf2(int[] a, int[] b) {  int n = a.Length, m = b.Length;  // If a[] has more elements, then call medianOf2   // with reversed parameters  if (n > m)  return medianOf2(b, a);  int lo = 0, hi = n;  while (lo <= hi) {  int mid1 = (lo + hi) / 2;  int mid2 = (n + m + 1) / 2 - mid1;  // Find elements to the left and right of partition in a[]  int l1 = (mid1 == 0 ? int.MinValue : a[mid1 - 1]);  int r1 = (mid1 == n ? int.MaxValue : a[mid1]);  // Find elements to the left and right of partition in b[]  int l2 = (mid2 == 0 ? int.MinValue : b[mid2 - 1]);  int r2 = (mid2 == m ? int.MaxValue : b[mid2]);  // If it is a valid partition  if (l1 <= r2 && l2 <= r1) {    // If the total elements are even, then median is   // the average of two middle elements  if ((n + m) % 2 == 0)  return (Math.Max(l1, l2) + Math.Min(r1, r2)) / 2.0;  // If the total elements are odd, then median is   // the middle element  else  return Math.Max(l1, l2);  }  // Check if we need to take lesser elements from arr1  if (l1 > r2)  hi = mid1 - 1;  // Check if we need to take more elements from arr1  else  lo = mid1 + 1;  }  return 0;  }  static void Main() {  int[] a = { 1, 12, 15, 26, 38 };  int[] b = { 2, 13, 17, 30, 45, 60 };  Console.WriteLine(medianOf2(a, b));  } } 

// JavaScript Program to find the median of two sorted arrays // of different size using Binary Search function medianOf2(a, b) {  let n = a.length, m = b.length;  // If a[] has more elements, then call medianOf2   // with reversed parameters  if (n > m)  return medianOf2(b, a);  let lo = 0, hi = n;  while (lo <= hi) {  let mid1 = Math.floor((lo + hi) / 2);  let mid2 = Math.floor((n + m + 1) / 2) - mid1;  // Find elements to the left and right of partition in a[]  let l1 = (mid1 === 0) ? -Infinity : a[mid1 - 1];  let r1 = (mid1 === n) ? Infinity : a[mid1];  // Find elements to the left and right of partition in b[]  let l2 = (mid2 === 0) ? -Infinity : b[mid2 - 1];  let r2 = (mid2 === m) ? Infinity : b[mid2];  // If it is a valid partition  if (l1 <= r2 && l2 <= r1) {  // If the total elements are even, then median is   // the average of two middle elements  if ((n + m) % 2 === 0)  return (Math.max(l1, l2) + Math.min(r1, r2)) / 2.0;  // If the total elements are odd, then median is   // the middle element  else  return Math.max(l1, l2);  }  // Check if we need to take lesser elements from a[]  if (l1 > r2)  hi = mid1 - 1;  // Check if we need to take more elements from a[]  else  lo = mid1 + 1;  }  return 0; } // Driver Code let a = [1, 12, 15, 26, 38]; let b = [2, 13, 17, 30, 45, 60]; console.log(medianOf2(a, b)); 

17

Time Complexity: O(log(min(m, n))), since binary search is applied on the smaller array.
Auxiliary Space: O(1)