Given two sorted arrays A and B of size n and m respectively. Find the median of the final sorted array obtained after merging the given two arrays or in other words, we say that find median of two sorted arrays.
( Expected time complexity: O(log(n)) )
Table of Contents
Approach 1 for Median of Two Sorted Arrays
Using the two-pointer method, create a merged sorted array of A and B.
Then simply find the median of that array.
C++ Program for Median of Two Sorted Arrays
#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
int k=n+m; // size of merged sorted array
int M[k]; // array which will store integers of A and B in ascending order
int i=0,j=0,in=0; // i is a pointer index for A
// j is a pointer index for B
// in is a pointer index for M
while(i<n || j<m){
if(i<n && j<m){
if(A[i]<B[j]){
M[in]=A[i];
i++;
}
else{
M[in]=B[j];
j++;
}
}
else{
if(i<n){
M[in]=A[i];
i++;
}
else{
M[in]=B[j];
j++;
}
}
in++;
}
if(k%2==0){
double m1 = M[k/2];
double m2 = M[(k/2)-1];
return (m1+m2)/2;
}
else{
double m1 = M[k/2];
return m1;
}
return -1;
}
int main(){
int n,m;
cin>>n>>m;
int A[n],B[m];
for(int i=0;i<n;i++){
cin>>A[i];
}
for(int i=0;i<m;i++){
cin>>B[i];
}
double median = findMedian(A,B,n,m);
cout<<median<<"\n";
}
5 5 6 1 2 7 8 3 4 5 6 7
3.5
Complexity Analysis
Time Complexity: O(max(n,m) because we find the merging sorted array by using the both arrays.
Space Complexity: O(n+m) because we store the final merged array that will lead us to O(n+m) space complexity.
Approach 2 for Median of Two Sorted Arrays
To solve this problem, we need to first understand what actually does the median do.
It is the partitioning of set into two equal length subsets such that one subset is greater than the other.
i.e., partition the set into two subsets such that every element of one subset is greater than every element of the other subset.
Now come back to the problem, we need to find the median of two sorted arrays.
Can we find a partition for array A and B, such that the length of subsets obtained by adding left of both partitions and right of both partitions are equal?
Partitioning an array at the ith position also denotes the number of elements from that array that are present in the left subset.
And as we know that the length of subsets obtained should be equal, hence
partitionA + partitionB = (length(A) +length(B)+1)/2
(If the length of the final merged sorted array is odd then, left subset would have more elements)
Now the only thing left is to check how to partition the given two arrays such that the right subset is greater than the left subset.
Let’s define the perfect partition of sorted arrays:
Let say we have array A( length n) and an array B( length m )
We have partitioned A at i and B at j, then
A perfect partition is when:
- i+j = (n+m+1)/2 (subsets are of equal length)
- A[i-1]<=B[j] (elements of A in the left of i will come in the left subset)
- B[j-1]<=A[i] (elements of B in the left of j will come in left subset)
If A[i-1]>B[j] that means there are some elements in the left of A’s partition that should be placed in the greater(right) subset. In that case, we will move i towards left and j towards the right.
If B[j-1]>A[i] that means there are some elements in the left of B’s partition which should be placed in the greater(right) subset. In that case, we will move j towards the left and i toward the right.
Now to move our partition pointers we can use binary search.
Explanation
Let’s understand it with an example:
Given two sorted arrays A and B.
Let’s start partitioning A using binary search and check if we can get a perfect partition or not.
Step 1
left=0
right=6
mid=(0+6)/2 = 3 (partition for A)
We can get the partition of B using partitionA + partitionB = (length(A) +length(B)+1)/2
partitionB= (6+4+1)/2 – partitionA
partitionB = 5-3 = 2
Left of B’s partition is greater than right of A’s partition. This means we have to add more elements of A for perfect partition.
Step 2
Do left=mid+1 i.e., left = 4
right=6
hence new mid = (4+6)/2 =5
partitionB =(6+4+1)/2 – partitionA
partitionB = 0
As left of A’s partition is greater than right of B’s partition. This means we should add more elements of B to get perfect partition.
Step 3
Do right = mid-1
Left = 4
right = 4
hence new mid = (4+4)/2 = 4
partitionB= (6+4+1)/2 – partitionA
partitionB = 1
Now we can see there are total 5 elements in the enclosed figure and total 5 elements outside it.
Also, the left of A’s partition is less than the right of B’s partition.
And the left of B’s partition is less than the right of A’s partition.
Hence our array will merge like this:
As our array is of even size hence the median will be obtained by taking average of middle two elements of final sorted array:
- One will be the maximum of the left side of perfect partition i.e., max(17,11).
- The second will be the minimum of the right side of perfect partition i.e., min(19,18).
Isn’t it?
Median obtained = (17+18)/2
= 17.5
If the length of the merged sorted array is odd, then the answer will simply be the maximum of the left side of the perfect partition.
Example
Input:
The first line of input contains two integers n and m, denoting the size of array A and B.
The next line contains n space-separated integers which denote A[i] where 0<=i<n.
The next line contains m space-separated integers which denote B[i] where 0<=i<m.
Output:
Print the median of given two sorted arrays.
C++ Program for Median of Two Sorted Arrays
#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
int left = 0, right = n;
while (left <= right) {
int partitionA = (left + right)/2;
int partitionB = (n + m + 1)/2 - partitionA; // partitionA + partitionB = (n+m+1)/2
//if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
double maxLeftA = INT_MIN;
if(partitionA > 0){
maxLeftA = A[partitionA-1];
}
//if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
double minRightA = INT_MAX;
if(partitionA < n){
minRightA = A[partitionA];
}
//Similarly for maxLeftB and minrightB
double maxLeftB = INT_MIN;
if(partitionB > 0){
maxLeftB = B[partitionB-1];
}
double minRightB = INT_MAX;
if(partitionB < m){
minRightB = B[partitionB];
}
if (maxLeftA <= minRightB && maxLeftB <= minRightA) { // check weather it's a perfect partition or not
if ((n+m) % 2 == 0) { // if the sorted merged array is of even length
return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2;
}
else {
return max(maxLeftA, maxLeftB);
}
}
else if (maxLeftA > minRightB) { //move left side.
right = partitionA - 1;
}
else { // move right side
left = partitionA + 1;
}
}
return -1; // we can't find the median if input is invalid i.e., arrays are not sorted
}
int main(){
int n,m;
cin>>n>>m;
int A[n],B[m];
for(int i=0;i<n;i++){
cin>>A[i];
}
for(int i=0;i<m;i++){
cin>>B[i];
}
double median = findMedian(A,B,n,m);
cout<<median<<"\n";
}4 5 1 2 7 8 3 4 5 6 7
5
JAVA Program for Median of Two Sorted Arrays
import java.util.Scanner;
public class Main{
public static double findMedian(int A[], int B[],int n,int m) {
int left = 0, right = n;
while (left <= right) {
int partitionA = (left + right)/2;
int partitionB = (n + m + 1)/2 - partitionA; // partitionA + partitionB = (n+m+1)/2
//if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
double maxLeftA = Integer.MIN_VALUE;
if(partitionA > 0){
maxLeftA = A[partitionA-1];
}
//if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
double minRightA = Integer.MAX_VALUE;
if(partitionA < n){
minRightA = A[partitionA];
}
//Similarly for maxLeftB and minrightB
double maxLeftB = Integer.MIN_VALUE;
if(partitionB > 0){
maxLeftB = B[partitionB-1];
}
double minRightB = Integer.MAX_VALUE;
if(partitionB < m){
minRightB = B[partitionB];
}
if (maxLeftA <= minRightB && maxLeftB <= minRightA) { // check weather it's a perfect partition or not
if ((n+m) % 2 == 0) { // if the sorted merged array is of even length
return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2;
}
else {
return Math.max(maxLeftA, maxLeftB);
}
}
else if (maxLeftA > minRightB) { //move left side.
right = partitionA - 1;
}
else { // move right side
left = partitionA + 1;
}
}
return -1; // we can't find the median if input is invalid i.e., arrays are not sorted
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n,m;
n = scan.nextInt();
m = scan.nextInt();
int A[]=new int[n];
int B[]=new int[m];
for(int i=0;i<n;i++){
A[i] = scan.nextInt();
}
for(int i=0;i<m;i++){
B[i] = scan.nextInt();
}
double median = findMedian(A,B,n,m);
System.out.println(median);
}
}4 6 6 7 8 9 1 2 3 4 5 6
5.5
Complexity Analysis for Median of Two Sorted Arrays
Time Complexity: O(log(n))
as at every step, we are reducing the search space by half (either choosing left search space or right search space from the middle index).
Space Complexity: O(1) because we just use some variables for calculation.
Thanks for reading!!