Median of two Sorted Arrays of Different Sizes

Given two sorted arrays, a[] and b[], 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], b[] = [2, 4, 5, 6, 7]
Output: 4.5
Explanation: The merged array is [1, 2, 4, 5, 6, 7]. 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 combines both sorted arrays into a new array and then sorts it. Once sorted, it finds the median by checking the total length. If the size is odd, it returns the middle element; if even, it returns the average of the two middle elements. This method is straightforward but not optimal in terms of time and space complexity.

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

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

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

import java.util.Collections; import java.util.Arrays; 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));  } } 

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)) 

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

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 

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

The idea is to simulate the merging process of two sorted arrays without actually creating a new one. By iterating through both arrays together until reaching the middle index, the algorithm keeps track of the last two selected elements.

These are then used to compute the median: if the total number of elements is odd, the middle element is returned; if even, the average of the two middle elements is returned. This ensures correct handling for both even and odd combined lengths.

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

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

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

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)) 

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

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 

[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(log n) 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.

#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 = { -5, 3, 6, 12, 15 };  vector<int> b = { -12, -10, -6, -3, 4, 10 };  cout << medianOf2(a, b);    return 0; } 

#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[] = {-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; } 

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 = {-5, 3, 6, 12, 15};  int[] b = {-12, -10, -6, -3, 4, 10};  System.out.println(medianOf2(a, b));  } } 

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 = [-5, 3, 6, 12, 15] b = [-12, -10, -6, -3, 4, 10] print(medianOf2(a, b)) 

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 = { -5, 3, 6, 12, 15 };  int[] b = { -12, -10, -6, -3, 4, 10 };  Console.WriteLine(medianOf2(a, b));  } } 

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 = [-5, 3, 6, 12, 15]; let b = [-12, -10, -6, -3, 4, 10]; console.log(medianOf2(a, b)); 

3