Median of Two Sorted Arrays of Same Size
Before getting into the problem statement of finding the median of two sorted arrays, let us first get a brief introduction about the arrays.
An array is a linear collection of values stored at contiguous memory locations. Array stores homogeneous values(similar data type values).
To learn more about the arrays, refer to the article – Arrays in Data Structure.
Note:
A list is used to store one or more objects or data elements. Lists are used in python and java mostly. We can say that lists are similar to arrays.
Median is the mid element (middle element) of an sorted array if the number of elements in the array is odd. If the number of elements in the array is even then the median is the average of the two middle elements.
Problem Statement
We are provided with two sorted arrays named array_1 and array_2 of size n each and we need to find the median of the array obtained after merging the provided two sorted arrays.
- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.
Constraints
- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $
Here, $ m == n $ as both the arrays are of same length.
In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.
The problem is to find the median of two sorted arrays.
Example
Let us look at some of the examples provided to find the median of two sorted arrays of same length.
Example 1:
Given, first input array is [ 1, 12, 15, 26, 38 ]
Given, second input array is [ 2, 13, 17, 30, 45 ]
Output:
The median of two sorted arrays is 16.0Example 2:
Given, first input the array is [ 1, 2 ]
Given, second input array is [ 3, 4 ]
Output:
The median of two sorted arrays is 2 (floor value of 2.5 is 2)Explanation
Let us take the first example and find the median of two sorted arrays.
The first array (a1) is [ 1, 12, 15, 26, 38 ]
The second array (a2) is [ 2, 13, 17, 30, 45 ]
After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]
The average of the two middle elements is:$ (15 + 17)/2 $ i.e. 16.
Note: The size of the first array is n then the size of the merged array is 2n and hence we need to take the average of the two middle elements.
Approach 1: Simply Count While Merging
The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.
We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.
Since there can be 2n elements in the array, whenever our counter reaches n, it means we have reached the median of the two arrays. We just need to take the average of the n th element and n+1th element as the size of the merged array is even.
Algorithm
The pseudo-code for the algorithm can be:
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
Implementation:
C++ code:
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point to the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point the
the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
Output:
The median of two sorted arrays is: 16
Complexity Analysis
In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.
Time Complexity
As we are traversing only the first n elements of the arrays, the time complexity is O(n).
Space Complexity
We are not using any extra space rather than a count variable. So, space complexity is O(1).
Approach 2: By Comparing the Medians of Two Arrays
In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function for finding median of array
int median(int a[], int n) {
// checking if length is even or odd
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
// base cases
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
// median of the first array
int m1 = median(a1, n);
// median of the second array
int m2 = median(a2, n);
if (m1 == m2)
return m1;
// if the first median is smaller then check further
if (m1 < m2) {
// if the length of the array is even, recursively call the function
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
// a function for finding median of array
static int median(int[] a, int start, int end) {
int n = end - start + 1;
// checking if length is even or odd
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
// a recursive function that returns the median of the array
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
// base case
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
// median of the first array
int m1 = median(a1, start_a1, end_a1);
// median of the second array
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
// if the median of the first array is smaller then recursively call the function
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}
Python code:
# a function for finding median of array
def median(a, n):
# checking if length is even or odd
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
# a recursive function that returns the median of the array
def findMedian(a1, a2, n):
# base cases
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
# median of the first array
m1 = median(a1, n)
# median of the second array
m2 = median(a2, n)
# if first median is larger then check further
if m1 > m2:
# if the length of array is even
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
# if first median is smaller then check further
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.
Time Complexity
So, the time complexity is O(log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Approach 3: By Taking Union w/o Extra Space
In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function that returns the median of the array.
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
// sorting both the arrays
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
import java.util.*;
public class Test {
// a function that returns the median of the array.
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1) {
// swapping
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
// sorting both the arrays
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
# a function that returns the median of the array.
def findMedian(a1, a2, n):
i, j = n - 1, 0
# union of both the arrays
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
# sorting both the arrays
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.
Time Complexity
So, the time complexity is O(n log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Median of Two Sorted Arrays of Different Sizes
So far we have seen the approaches of finding the median of two sorted arrays of the same length.
Let us now discuss a variance of this problem where the size of both the arrays is not the same.
Problem Statement
We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.
- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.
Constraints
- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $
Here, $ m == n $ as both the arrays are of same length.
In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.
The problem is to find the median of two sorted arrays.
Example
Let us look at some of the examples provided to find the median of two sorted arrays of same length.
Example 1:
Given, first input array is [ 1, 12, 15, 26, 38 ]
Given, second input array is [ 2, 13, 17, 30, 45 ]
Output:
The median of two sorted arrays is 16.0Example 2:
Given, first input the array is [ 1, 2 ]
Given, second input array is [ 3, 4 ]
Output:
The median of two sorted arrays is 2 (floor value of 2.5 is 2)Explanation
Let us take the first example and find the median of two sorted arrays.
The first array (a1) is [ 1, 12, 15, 26, 38 ]
The second array (a2) is [ 2, 13, 17, 30, 45 ]
After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]
The average of the two middle elements is:$ (15 + 17)/2 $ i.e. 16.
Note: The size of the first array is n then the size of the merged array is 2n and hence we need to take the average of the two middle elements.
Approach 1: Simply Count While Merging
The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.
We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.
Since there can be 2n elements in the array, whenever our counter reaches n, it means we have reached the median of the two arrays. We just need to take the average of the n th element and n+1th element as the size of the merged array is even.
Algorithm
The pseudo-code for the algorithm can be:
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
Implementation:
C++ code:
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point to the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point the
the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
Output:
The median of two sorted arrays is: 16
Complexity Analysis
In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.
Time Complexity
As we are traversing only the first n elements of the arrays, the time complexity is O(n).
Space Complexity
We are not using any extra space rather than a count variable. So, space complexity is O(1).
Approach 2: By Comparing the Medians of Two Arrays
In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function for finding median of array
int median(int a[], int n) {
// checking if length is even or odd
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
// base cases
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
// median of the first array
int m1 = median(a1, n);
// median of the second array
int m2 = median(a2, n);
if (m1 == m2)
return m1;
// if the first median is smaller then check further
if (m1 < m2) {
// if the length of the array is even, recursively call the function
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
// a function for finding median of array
static int median(int[] a, int start, int end) {
int n = end - start + 1;
// checking if length is even or odd
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
// a recursive function that returns the median of the array
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
// base case
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
// median of the first array
int m1 = median(a1, start_a1, end_a1);
// median of the second array
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
// if the median of the first array is smaller then recursively call the function
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}
Python code:
# a function for finding median of array
def median(a, n):
# checking if length is even or odd
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
# a recursive function that returns the median of the array
def findMedian(a1, a2, n):
# base cases
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
# median of the first array
m1 = median(a1, n)
# median of the second array
m2 = median(a2, n)
# if first median is larger then check further
if m1 > m2:
# if the length of array is even
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
# if first median is smaller then check further
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.
Time Complexity
So, the time complexity is O(log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Approach 3: By Taking Union w/o Extra Space
In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function that returns the median of the array.
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
// sorting both the arrays
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
import java.util.*;
public class Test {
// a function that returns the median of the array.
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1) {
// swapping
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
// sorting both the arrays
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
# a function that returns the median of the array.
def findMedian(a1, a2, n):
i, j = n - 1, 0
# union of both the arrays
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
# sorting both the arrays
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.
Time Complexity
So, the time complexity is O(n log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Median of Two Sorted Arrays of Different Sizes
So far we have seen the approaches of finding the median of two sorted arrays of the same length.
Let us now discuss a variance of this problem where the size of both the arrays is not the same.
Problem Statement
We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.
- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.
Constraints
- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $
Here, $ m == n $ as both the arrays are of same length.
In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.
The problem is to find the median of two sorted arrays.
Example
Let us look at some of the examples provided to find the median of two sorted arrays of same length.
Example 1:
Given, first input array is [ 1, 12, 15, 26, 38 ]
Given, second input array is [ 2, 13, 17, 30, 45 ]
Output:
The median of two sorted arrays is 16.0Example 2:
Given, first input the array is [ 1, 2 ]
Given, second input array is [ 3, 4 ]
Output:
The median of two sorted arrays is 2 (floor value of 2.5 is 2)Explanation
Let us take the first example and find the median of two sorted arrays.
The first array (a1) is [ 1, 12, 15, 26, 38 ]
The second array (a2) is [ 2, 13, 17, 30, 45 ]
After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]
The average of the two middle elements is:$ (15 + 17)/2 $ i.e. 16.
:::section{.tip}
Note: The size of the first array is n then the size of the merged array is 2n and hence we need to take the average of the two middle elements.
Approach 1: Simply Count While Merging
The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.
We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.
Since there can be 2n elements in the array, whenever our counter reaches n, it means we have reached the median of the two arrays. We just need to take the average of the n th element and n+1th element as the size of the merged array is even.
Algorithm
The pseudo-code for the algorithm can be:
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
Implementation:
C++ code:
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point to the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point the
the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
Output:
The median of two sorted arrays is: 16
Complexity Analysis
In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.
Time Complexity
As we are traversing only the first n elements of the arrays, the time complexity is O(n).
Space Complexity
We are not using any extra space rather than a count variable. So, space complexity is O(1).
Approach 2: By Comparing the Medians of Two Arrays
In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function for finding median of array
int median(int a[], int n) {
// checking if length is even or odd
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
// base cases
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
// median of the first array
int m1 = median(a1, n);
// median of the second array
int m2 = median(a2, n);
if (m1 == m2)
return m1;
// if the first median is smaller then check further
if (m1 < m2) {
// if the length of the array is even, recursively call the function
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
// a function for finding median of array
static int median(int[] a, int start, int end) {
int n = end - start + 1;
// checking if length is even or odd
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
// a recursive function that returns the median of the array
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
// base case
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
// median of the first array
int m1 = median(a1, start_a1, end_a1);
// median of the second array
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
// if the median of the first array is smaller then recursively call the function
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}
Python code:
# a function for finding median of array
def median(a, n):
# checking if length is even or odd
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
# a recursive function that returns the median of the array
def findMedian(a1, a2, n):
# base cases
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
# median of the first array
m1 = median(a1, n)
# median of the second array
m2 = median(a2, n)
# if first median is larger then check further
if m1 > m2:
# if the length of array is even
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
# if first median is smaller then check further
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.
Time Complexity
So, the time complexity is O(log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Approach 3: By Taking Union w/o Extra Space
In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function that returns the median of the array.
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
// sorting both the arrays
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
import java.util.*;
public class Test {
// a function that returns the median of the array.
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1) {
// swapping
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
// sorting both the arrays
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
# a function that returns the median of the array.
def findMedian(a1, a2, n):
i, j = n - 1, 0
# union of both the arrays
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
# sorting both the arrays
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.
Time Complexity
So, the time complexity is O(n log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Median of Two Sorted Arrays of Different Sizes
So far we have seen the approaches of finding the median of two sorted arrays of the same length.
Let us now discuss a variance of this problem where the size of both the arrays is not the same.
Problem Statement
We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.
- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.
Constraints
- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $
Here, $ m == n $ as both the arrays are of same length.
In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.
The problem is to find the median of two sorted arrays.
Example
Let us look at some of the examples provided to find the median of two sorted arrays of same length.
Example 1:
Given, first input array is [ 1, 12, 15, 26, 38 ]
Given, second input array is [ 2, 13, 17, 30, 45 ]
Output:
The median of two sorted arrays is 16.0Example 2:
Given, first input the array is [ 1, 2 ]
Given, second input array is [ 3, 4 ]
Output:
The median of two sorted arrays is 2 (floor value of 2.5 is 2)Explanation
Let us take the first example and find the median of two sorted arrays.
The first array (a1) is [ 1, 12, 15, 26, 38 ]
The second array (a2) is [ 2, 13, 17, 30, 45 ]
After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]
The average of the two middle elements is:$ (15 + 17)/2 $ i.e. 16.
:::section{.tip}
Note: The size of the first array is n then the size of the merged array is 2n and hence we need to take the average of the two middle elements.
Approach 1: Simply Count While Merging
The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.
We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.
Since there can be 2n elements in the array, whenever our counter reaches n, it means we have reached the median of the two arrays. We just need to take the average of the n th element and n+1th element as the size of the merged array is even.
Algorithm
The pseudo-code for the algorithm can be:
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
Implementation:
C++ code:
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point to the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
/*
i will point to the current index of the first array and j will point the
the current index of the second array
*/
int i = 0;
int j = 0;
/*
a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
*/
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
/*
when all elements of a1[] are smaller than smallest than the first element of a2[]
*/
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
/*
when all elements of a2[] are smaller than smallest than the first element of a1[]
*/
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
Output:
The median of two sorted arrays is: 16
Complexity Analysis
In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.
Time Complexity
As we are traversing only the first n elements of the arrays, the time complexity is O(n).
Space Complexity
We are not using any extra space rather than a count variable. So, space complexity is O(1).
Approach 2: By Comparing the Medians of Two Arrays
In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function for finding median of array
int median(int a[], int n) {
// checking if length is even or odd
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
// base cases
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
// median of the first array
int m1 = median(a1, n);
// median of the second array
int m2 = median(a2, n);
if (m1 == m2)
return m1;
// if the first median is smaller then check further
if (m1 < m2) {
// if the length of the array is even, recursively call the function
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
public class Test {
// a function for finding median of array
static int median(int[] a, int start, int end) {
int n = end - start + 1;
// checking if length is even or odd
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
// a recursive function that returns the median of the array
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
// base case
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
// median of the first array
int m1 = median(a1, start_a1, end_a1);
// median of the second array
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
// if the median of the first array is smaller then recursively call the function
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}
Python code:
# a function for finding median of array
def median(a, n):
# checking if length is even or odd
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
# a recursive function that returns the median of the array
def findMedian(a1, a2, n):
# base cases
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
# median of the first array
m1 = median(a1, n)
# median of the second array
m2 = median(a2, n)
# if first median is larger then check further
if m1 > m2:
# if the length of array is even
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
# if first median is smaller then check further
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.
Time Complexity
So, the time complexity is O(log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Approach 3: By Taking Union w/o Extra Space
In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function that returns the median of the array.
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
// sorting both the arrays
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}
Java code:
import java.util.*;
public class Test {
// a function that returns the median of the array.
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
// union of both the arrays
while (a1[i] > a2[j] && j < n && i > -1) {
// swapping
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
// sorting both the arrays
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}
Python code:
# a function that returns the median of the array.
def findMedian(a1, a2, n):
i, j = n - 1, 0
# union of both the arrays
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
# sorting both the arrays
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))
Output:
The median of two sorted arrays is: 5
Complexity Analysis
In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.
Time Complexity
So, the time complexity is O(n log n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Median of Two Sorted Arrays of Different Sizes
So far we have seen the approaches of finding the median of two sorted arrays of the same length.
Let us now discuss a variance of this problem where the size of both the arrays is not the same.
Problem Statement
We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.
- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.
Constraints
- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $
In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.
The problem is to find the median of two sorted arrays of different lengths.
Example
Let us look at some of the examples provided to find the second largest element in the array.
Example 1: Given first input array is [ -5, 3, 6, 12, 15 ] Given second input array is [ -12, -10, -6, -3, 4, 10 ] Output:
The median of two sorted arrays is 3
Example 2: Given the first input, array is [ 2, 3, 5, 8 ] Given second input array is [ 10, 12, 14, 16, 18, 20 ]
Output:
The median of two sorted arrays is 11
Example Explanation
Let us take the first example and find the median of two sorted arrays.
The first array (a1) is [ -5, 3, 6, 12, 15 ] The second array (a2) is [ -12, -10, -6, -3, 4, 10 ]
After merging these two arrays, the merged array is [ -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 ]
The median of the array is 3 as the size of the merged array is 11 so the median is present at the 5th index i.e. 11/2 (floor value comes out to be 5).
Approach 1: Linear and Simpler Approach
The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.
We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.
The size of the merged array can be even or odd. Let us see both the cases:
- If the size of the array is odd (i.e. m+nm+n is odd) then median is obtained as (m+n)/2(m+n)/2.
- If the size of the array is even (i.e. m + n is even) then the median is obtained as the average of (m+n)/2−1(m+n)/2−1 and (m+n)/2(m+n)/2.
Algorithm
The pseudo-code for the algorithm can be:
1. Merge the two input arrays and initialize a counter variable.
2. Take two variables i, and j. i points to the starting index of the first array and j points to the starting index of the second array.
3. If the size of the array is odd then:
- Traverse the array and when the counter reaches (m + n)/2, stop the counter and return the result as a[(m + n)/2].
4. Else:
- Traverse the array and when the counter reaches (m + n)/2, stop the counter and return the result as the average of elements at index (m+n)/2 and ((m+n)/2 – 1).
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function to return the median of the array
int findMedian(int a1[], int a2[], int n, int m) {
/*
i points to the starting index of the first array and j points to the starting index of the second array.
*/
int i = 0;
int j = 0;
int count;
int firstMedian = -1, secondMedian = -1;
// If the size of the array is odd then traverse the array and when the counter reaches (m + n)/2.
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
}
else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return firstMedian;
}
// otherwise, traverse the array and when the counter reaches (m + n)/2.
else {
for (count = 0; count <= (n + m) / 2; count++) {
secondMedian = firstMedian;
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
}
else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return (firstMedian + secondMedian) / 2;
}
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1, n2);
return 0;
}
Java code:
public class Test {
// a function to return the median of the array
static int findMedian(int a1[], int a2[], int n, int m) {
/*
i points to the starting index of the first array and j points to the starting index of the second array.
*/
int i = 0;
int j = 0;
int count;
int firstMedian = -1, secondMedian = -1;
// If the size of the array is odd then traverse the array and when the counter reaches (m + n)/2.
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
} else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return firstMedian;
}
// otherwise, traverse the array and when the counter reaches (m + n)/2.
else {
for (count = 0; count <= (n + m) / 2; count++) {
secondMedian = firstMedian;
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
} else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return (firstMedian + secondMedian) / 2;
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length, a2.length));
}
}
Python code:
# a function to return the median of the array
def findMedian(a1, a2, n, m):
"""
i points to the starting index of the first array and j points to the starting index of the second array.
"""
i = 0
j = 0
firstMedian, secondMedian = -1, -1
# If the size of the array is odd then traverse the array and when the counter reaches (m + n)/2.
if((m + n) % 2 == 1):
for count in range(((n + m) // 2) + 1):
if(i != n and j != m):
if a1[i] > a2[j]:
firstMedian = a2[j]
j += 1
else:
firstMedian = a1[i]
i += 1
elif(i < n):
firstMedian = a1[i]
i += 1
else:
firstMedian = a2[j]
j += 1
return firstMedian
# otherwise, traverse the array and when the counter reaches (m + n)/2.
else:
for count in range(((n + m) // 2) + 1):
secondMedian = firstMedian
if(i != n and j != m):
if a1[i] > a2[j]:
firstMedian = a2[j]
j += 1
else:
firstMedian = a1[i]
i += 1
elif(i < n):
firstMedian = a1[i]
i += 1
else:
firstMedian = a2[j]
j += 1
return (firstMedian + secondMedian)//2
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1), len(a2))))
Output:
The median of two sorted arrays is: 6
Complexity Analysis
In this basic approach to finding the median of two sorted arrays of different lengths, we have traversed the arrays and counted the first m + n sorted elements of the merged array.
Time Complexity
As we are traversing only the first m + n elements of the arrays, the time complexity is O(m + n).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Approach 2: Efficient Solution
An efficient approach of finding the median of two sorted arrays of varying sizes can be finding the median of both the arrays and then discarding the one half (sub-array) of both the arrays. Let us see the algorithm and code for a better understanding.
Algorithm
The pseudo-code for the algorithm can be:
1. Create a recursive function that takes both arrays.
2. Find the median of both the arrays and compare them.
3. If the median of the smaller array is lesser than the median of the larger array then we discard the first half of smaller array & second half of the larger array and vice versa.
4. Repeat the procedure by dividing the array into smaller sub-arrays and finally returning the result.
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// A function that returns the median of two integers
float medianOfTwo(int a, int b) {
return (a + b) / 2.0;
}
// A function that returns the median of three integers
float medianOfThree(int a, int b, int c) {
return a + b + c - max(a, max(b, c)) - min(a, min(b, c));
}
// A function that returns the median of four integers
float medianOfFour(int a, int b, int c, int d) {
int MAX = max(a, max(b, max(c, d)));
int MIN = min(a, min(b, min(c, d)));
return (a + b + c + d - MAX - MIN) / 2.0;
}
// A function that returns the median of an array
float medianSingle(int a[], int n) {
if (n == 0)
return -1;
if (n % 2 == 0)
return (double)(a[n / 2] + a[n / 2 - 1]) / 2;
return a[n / 2];
}
// A utility function that deals with the case when n1 is smaller than or equal to n2.
float findMedianUtil(int A[], int n1, int B[], int n2) {
// When the smaller array is empty
if (n1 == 0)
return medianSingle(B, n2);
// When the smaller array has only one element
if (n1 == 1) {
// Case 1: When the larger array has only one element
if (n2 == 1)
return medianOfTwo(A[0], B[0]);
// Case 2: When the larger array has odd number of elements
if (n2 & 1)
return medianOfTwo(B[n2 / 2], medianOfThree(A[0], B[n2 / 2 - 1], B[n2 / 2 + 1]));
// Case 3: When the larger array has even number of elements
return medianOfThree(B[n2 / 2], B[n2 / 2 - 1], A[0]);
}
// When the smaller array has two elements
else if (n1 == 2) {
// Case 4: When the larger array has two elements
if (n2 == 2)
return medianOfFour(A[0], A[1], B[0], B[1]);
// Case 5: When the larger array has odd number of elements
if (n2 & 1)
return medianOfThree(B[n2 / 2],
max(A[0], B[n2 / 2 - 1]),
min(A[1], B[n2 / 2 + 1]));
// Case 6: When the larger array has even number of elements
return medianOfFour(B[n2 / 2],
B[n2 / 2 - 1],
max(A[0], B[n2 / 2 - 2]),
min(A[1], B[n2 / 2 + 1]));
}
int indexA = (n1 - 1) / 2;
int indexB = (n2 - 1) / 2;
if (A[indexA] <= B[indexB])
return findMedianUtil(A + indexA, n1 / 2 + 1, B, n2 - indexA);
return findMedianUtil(A, n1 / 2 + 1, B + indexA, n2 - indexA);
}
float findMedian(int A[], int B[], int n1, int n2) {
if (n1 > n2)
return findMedianUtil(B, n2, A, n1);
return findMedianUtil(A, n1, B, n2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1, n2);
return 0;
}
Java code:
import java.util.*;
public class Test {
static double medianOfTwo(double a, double b) {
return (a + b) / 2.0;
}
// A function that returns the median of three integers
static double medianOfThree(double a, double b, double c) {
return a + b + c - Math.max(a, Math.max(b, c)) - Math.min(a, Math.min(b, c));
}
// A function that returns the median of four integers
static double medianOfFour(int a, int b, int c, int d) {
int MAX = Math.max(a, Math.max(b, Math.max(c, d)));
int MIN = Math.min(a, Math.min(b, Math.min(c, d)));
return (a + b + c + d - MAX - MIN) / 2.0;
}
// A function that returns the median of an array
static double medianSingle(int a[], int n) {
if (n == 0)
return -1;
if (n % 2 == 0)
return (double) (a[n / 2] + a[n / 2 - 1]) / 2;
return a[n / 2];
}
// A utility function that deals with the case when n1 is smaller than or equal
// to n2.
static double findMedianUtil(int A[], int n1, int B[], int n2) {
// When the smaller array is empty
if (n1 == 0)
return medianSingle(B, n2);
// When the smaller array has only one element
if (n1 == 1) {
// Case 1: When the larger array has only one element
if (n2 == 1)
return medianOfTwo(A[0], B[0]);
// Case 2: When the larger array has odd number of elements
if (n2 % 2 != 0)
return medianOfTwo(B[n2 / 2], medianOfThree(A[0], B[n2 / 2 - 1], B[n2 / 2 + 1]));
// Case 3: When the larger array has even number of elements
return medianOfThree(B[n2 / 2], B[n2 / 2 - 1], A[0]);
}
// When the smaller array has two elements
else if (n1 == 2) {
// Case 4: When the larger array has two elements
if (n2 == 2)
return medianOfFour(A[0], A[1], B[0], B[1]);
// Case 5: When the larger array has odd number of elements
if (n2 % 2 != 0)
return medianOfThree(B[n2 / 2],
Math.max(A[0], B[n2 / 2 - 1]),
Math.min(A[1], B[n2 / 2 + 1]));
// Case 6: When the larger array has even number of elements
return medianOfFour(B[n2 / 2],
B[n2 / 2 - 1],
Math.max(A[0], B[n2 / 2 - 2]),
Math.min(A[1], B[n2 / 2 + 1]));
}
int indexA = (n1 - 1) / 2;
int indexB = (n2 - 1) / 2;
if (A[indexA] <= B[indexB])
return findMedianUtil(Arrays.copyOfRange(A, indexA, A.length), n1 / 2 + 1, B, n2 - indexA);
return findMedianUtil(A, n1 / 2 + 1, Arrays.copyOfRange(B, indexB, B.length), n2 - indexA);
}
static double findMedian(int A[], int B[], int n1, int n2) {
if (n1 > n2)
return findMedianUtil(B, n2, A, n1);
return findMedianUtil(A, n1, B, n2);
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length, a2.length));
}
}
Python code:
# A function that returns the median of two integers
def medianOfTwo(a, b):
return (a + b) / 2
# A utility function to find median of three integers
def medianOfThree(a, b, c):
return a + b + c - max(a, max(b, c)) - min(a, min(b, c))
# A utility function to find a median of four integers
def medianOfFour(a, b, c, d):
MAX = max(a, max(b, max(c, d)))
MIN = min(a, min(b, min(c, d)))
return (a + b + c + d - MAX - MIN) / 2
# A function that returns the median of an array
def medianSingle(a, n):
if (n == 0):
return -1
if (n % 2 == 0):
return (a[n // 2] + a[n // 2 - 1]) / 2
return a[n // 2]
# A utility function that deals with the case when n1 is smaller than or equal to n2.
def findMedianUtil(A, n1, B, n2):
# When the smaller array is empty
if (n1 == 0):
return medianSingle(B, n2)
# When the smaller array has only one element
if (n1 == 1):
# Case 1: When the larger array has only one element
if (n2 == 1):
return medianOfTwo(A[0], B[0])
# Case 2: When the larger array has odd number of elements
if (n2 & 1 != 0):
return medianOfTwo(B[n2 // 2], medianOfThree(A[0], B[n2 // 2 - 1], B[n2 // 2 + 1]))
# Case 3: When the larger array has even number of elements
return medianOfThree(B[n2 // 2], B[n2 // 2 - 1], A[0])
# When the smaller array has two elements
elif (n1 == 2):
# Case 4: When the larger array has two elements
if (n2 == 2):
return medianOfFour(A[0], A[1], B[0], B[1])
# Case 5: When the larger array has odd number of elements
if (n2 & 1 != 0):
return medianOfThree(B[n2 // 2], max(A[0], B[n2 // 2 - 1]), min(A[1], B[n2 // 2 + 1]))
# Case 6: When the larger array has even number of elements
return medianOfFour(B[n2 // 2], B[n2 // 2 - 1], max(A[0], B[n2 // 2 - 2]), min(A[1], B[n2 // 2 + 1]))
indexA = (n1 - 1) // 2
indexB = (n2 - 1) // 2
if (A[int(indexA)] <= B[int(indexB)]):
return findMedianUtil(A + indexA, n1 // 2 + 1, B, n2 - indexA)
return findMedianUtil(A, n1 // 2 + 1, B + indexA, n2 - indexA)
def findMedian(A, n1, B, n2):
if n1 > n2:
return findMedianUtil(B, n2, A, n1)
return findMedianUtil(A, n1, B, n2)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
print("The median of two sorted arrays is: ",
int(findMedian(a1, len(a1), a2, len(a2))))
Output:
The median of two sorted arrays is: 6
Complexity Analysis
In this approach to finding the median of two sorted arrays of different lengths, we have used the divide and conquer technique as in each step, we are discarding one-half of the array.
Time Complexity
So, the time complexity is O(min(log m, log n)).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Approach 3: Simple Mathematical Approach
In this approach of finding the median of two sorted arrays can be merging the two arrays into a single array and then sorting the resulting array. Now depending upon the size of the resultant array, we can easily find the median and return it.
Algorithm
The pseudo-code for the algorithm can be:
1. Merge the two arrays into a single array.
2. Sort the resulting array.
3. If the size of the resulting array is odd:
return a[length/2]
Else:
return (a[length/2] + a[(length/2) - 1]) / 2
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a[], int n) {
// When length of array is even
if (n % 2 == 0) {
int z = n / 2;
int e = a[z];
int q = a[z - 1];
int result = (e + q) / 2;
return result;
}
// When the length of the array is odd
else {
int z = round(n / 2);
return a[z];
}
}
int main()
{
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
int n = n1 + n2;
int a3[n];
// merging both the arrays
for (int i = 0; i < n1; i++)
a3[i] = a1[i];
int j = 0;
for (int i = n1; i < n; i++)
a3[i] = a2[j++];
// Sorting the merged arrays
sort(a3, a3 + n);
cout << "The median of two sorted arrays is: " << findMedian(a3, n);
return 0;
}
Java code:
import java.util.*;
public class Test {
static int findMedian(int a[], int n) {
// When length of array is even
if (n % 2 == 0) {
int z = n / 2;
int e = a[z];
int q = a[z - 1];
int result = (e + q) / 2;
return result;
}
// When length of array is odd
else {
int z = Math.round(n / 2);
return a[z];
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
int n1 = a1.length;
int n2 = a2.length;
int n = n1 + n2;
int a3[] = new int[n];
// merging both the arrays
System.arraycopy(a1, 0, a3, 0, n1);
System.arraycopy(a2, 0, a3, n1, n2);
// Sorting the merged arrays
Arrays.sort(a3);
System.out.println(
"The median of two sorted arrays is: " + findMedian(a3, n));
}
}
Python code:
def findMedian(a, n):
# When the length of the array is even
if n % 2 == 0:
z = n // 2
e = a[z]
q = a[z - 1]
result = (e + q) / 2
return result
# When length of array is odd
else:
z = n // 2
result = a[z]
return result
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
# merging both the arrays
a3 = a1 + a2
# Sorting the merged arrays
a3.sort()
print("The median of two sorted array is: ",
findMedian(a3, len(a3)))
Output:
The median of two sorted arrays is: 6
Complexity Analysis
In this approach of finding the median of two sorted arrays of different lengths, we have merged both the input arrays into a merged array, we are then finding the mid element of the merged array according to the size of the array.
Time Complexity
So, the time complexity is O((n+m) log (n+m)).
Space Complexity
We are using a merged array as extra space. So, space complexity is O(n + m).
Approach 4: Binary Search
Another efficient approach to finding the median of two sorted arrays can be applying binary search and dividing the arrays into halves and finding the required median.
In this approach, we are not merging the array and performing a binary search but we are using the algorithm specified below.
Let us assume that we are provided two input arrays of varying lengths A, and B. (Here, the first array i.e. A is smaller in size). The size of the array A is n and the size of array B is m.
For example, array A = [ 1, 4, 7 ] and array B = [ 2, 3, 5, 6 ]
Let us see the algorithm using the above example.
We can say that the sum of the left part of both array A and array B will result in the left part of the resultant merged array.
Similarly, the sum of the right part of both array A and array B will result in the right part of the resultant merged array.
The merged array will be [ 1, 2, 3, 4, 5, 6, 7 ]
In this example, our median is 4. So, we can easily discard the right half of the combined array. Hence, in this approach, we will try to discard the part of the array that will not contain our answer.
Algorithm
The pseudo-code for the algorithm can be:
1. Find the mid part i.e. (n + m – 1) / 2.
2. If A[i-1] <= B[j] and B[j-1]<=A[i] then return the i index.
3. Else if A[i – 1] > B[j], then we need to goto the left and update i to mid - 1.
4. Repeat the above process.
Implementation
C++ code:
#include <bits/stdc++.h>
using namespace std;
// a function that return the median of the two arrays
double findMedian(vector<int> &A, vector<int> &B) {
int n = A.size();
int m = B.size();
// if the first array is larger then swap
if (n > m)
return findMedian(B, A);
int start = 0;
int end = n;
int mergedMid = (n + m + 1) / 2;
while (start <= end) {
// we are using MIN and MIX to maintain the overflow range
// checking overflow of indices
int mid = (start + end) / 2;
int A_left_size = mid;
int B_left_size = mergedMid - mid;
int A_left = (A_left_size > 0)
? A[A_left_size - 1]
: INT_MIN;
int B_left = (B_left_size > 0) ? B[B_left_size - 1] : INT_MIN;
int A_right = (A_left_size < n) ? A[A_left_size] : INT_MAX;
int B_right = (B_left_size < m) ? B[B_left_size] : INT_MAX;
// if the correct partioning is done then check further else change the start or end pointer
if (A_left <= B_right and B_left <= A_right) {
if ((m + n) % 2 == 0)
return (max(A_left, B_left) + min(A_right, B_right)) / 2.0;
return max(A_left, B_left);
}
else if (A_left > B_right) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
int main() {
vector<int> a1 = {1, 2, 3, 6};
vector<int> a2 = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2);
return 0;
}
Java code:
public class Test {
// a function that return the median of the two arrays
static double findMedian(int[] A, int[] B) {
int n = A.length;
int m = B.length;
// if the first array is larger then swap
if (n > m)
return findMedian(B, A);
int start = 0;
int end = n;
int mergedMid = (n + m + 1) / 2;
while (start <= end) {
// we are using MIN and MIX to maintain the overflow range
// checking overflow of indices
int mid = (start + end) / 2;
int A_left_size = mid;
int B_left_size = mergedMid - mid;
int A_left = (A_left_size > 0)
? A[A_left_size - 1]
: Integer.MIN_VALUE;
int B_left = (B_left_size > 0) ? B[B_left_size - 1] : Integer.MIN_VALUE;
int A_right = (A_left_size < n) ? A[A_left_size] : Integer.MAX_VALUE;
int B_right = (B_left_size < m) ? B[B_left_size] : Integer.MAX_VALUE;
// if the correct partioning is done then check further else change the start or end pointer
if (A_left <= B_right && B_left <= A_right) {
if ((m + n) % 2 == 0)
return (Math.max(A_left, B_left)
+ Math.min(A_right, B_right))
/ 2.0;
return Math.max(A_left, B_left);
} else if (A_left > B_right) {
end = mid - 1;
} else
start = mid + 1;
}
return 0.0;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2));
}
}
Python code:
# a function that return the median of the two arrays
def findMedian(A, B):
n = len(A)
m = len(B)
# if the first array is larger then swap
# checking overflow of indices
if (n > m):
return findMedian(B, A)
start = 0
end = n
mergedMid = (n + m + 1) // 2
while (start <= end):
"""
we are using MIN and MIX to maintain the overflow range.
"""
mid = (start + end) // 2
A_left_size = mid
B_left_size = mergedMid - mid
A_left = A[A_left_size - 1] if (A_left_size > 0) else float('-inf')
B_left = B[B_left_size - 1] if (B_left_size > 0) else float('-inf')
A_right = A[A_left_size] if (A_left_size < n) else float('inf')
B_right = B[B_left_size] if (B_left_size < m) else float('inf')
# if the correct partioning is done then check further else change the start or end pointer
if A_left <= B_right and B_left <= A_right:
if ((m + n) % 2 == 0):
return (max(A_left, B_left) + min(A_right, B_right)) / 2.0
return max(A_left, B_left)
elif (A_left > B_right):
end = mid - 1
else:
start = mid + 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
print("The median of two sorted array is: ",
findMedian(a1, a2))
Output:
The median of two sorted array is: 6
Complexity Analysis
In this approach to finding the median of two sorted arrays of different lengths, we have performed a binary search on the array.
Time Complexity
So, the time complexity is O(min(log m, log n)).
Space Complexity
We are not using any extra space. So, space complexity is O(1).
Conclusion
- The most basic approach to finding the median of two sorted arrays of the same length can be counting the first n sorted elements of the merged array. In this approach, the time complexity is O(n) and space complexity is O(1).
- Another approach to finding the medians of two sorted arrays of the same length, can be finding the medians of both the arrays and then comparing them. In this approach, the time complexity is O(log n) and space complexity is O(1).
- Another approach to finding the medians of two sorted arrays of the same length first can be finding the union of both the arrays and then sorting them respectively. In this approach, the time complexity is O(n log n) and space complexity is O(1).
- The basic approach to finding the median of two sorted arrays of different lengths can be counting the first n sorted elements of the merged array. In this approach, the time complexity is O(m + n) and space complexity is O(1).
- Another approach to finding the median of two sorted arrays of different lengths can be finding the median of both the arrays and then discarding the one half (sub-array) of both the arrays. In this approach, the time complexity is O(min(log m, log n) and space complexity is O(1).
- Another approach to finding the median of two sorted arrays of different lengths can be merging the two arrays into a single array and then sorting it. Now, we can easily find the median and return it. In this approach, the time complexity is O((n+m) log (n+m)) and space complexity is O(n + m).
- Another approach to finding the median of two sorted arrays of different lengths can be applying binary search and diving the arrays into halves and finding the required median. In this approach, the time complexity is O(min(log m, log n)) and space complexity is O(1).
