Objective: Given two sorted arrays of size n. Write an algorithm to find the median of combined array (merger of both the given arrays, size = 2n).
What is Median?
The median is the value separating the higher half of a data sample, a population, or a probability distribution, from the lower half. For a data set, it may be thought of as the “middle” value. For example, in the data set {1, 3, 3, 6, 7, 8, 9}, the median is 6, the fourth largest, and also the fourth smallest, number in the sample. For a continuous probability distribution, the median is the value such that a number is equally likely to fall above or below it.
If n is odd then Median (M) = value of ((n + 1)/2)th item term.
If n is even then Median (M) = value of [(n/2)th item term + (n/2 + 1)th item term]/2
Reference: https://en.wikipedia.org/wiki/Median
Example
A = 2, 6, 9 B = 1, 5, 7 Median = (5+6)/2 = 5.5 Explanation: combined array: 1, 2, 5, 6, 7, 9
Approach:
Naïve: Create third array, which will be the merger of both the arrays based upon the formula we have mentioned above calculate the median.
Time Complexity: O(n)
Binary Approach: Compare the medians of both arrays
- Say arrays are array1[] and array2[].
- Calculate the median of both the arrays, say m1 and m2 for array1[] and array2[].
- If m1 == m2 then return m1 or m2 as final result.
- If m1 > m2 then median will be present in either of the sub arrays.
- Array1[] – from first element to m1.
- Array2[] – from m2 to last element.
- If m2 > m1 then median will be present in either of the sub arrays.
- Array1[] – from m1 to last element.
- Array2[] – from first element to m2.
- Repeat the steps from 1 to 5 recursively until 2 elements are left in both the arrays.
- Then apply the formula to get the median
- Median = (max(array1[0],array2[0]) + min(array1[1],array2[1]))/2
Let take an example and walk through-
int [] a = {2,6,9,10,11}; int [] b = {1,5,7,12,15}; m1 = 9 , m2 = 7 We have m1 > m2 Array1[] - from first element to m1, Array2[] – from m2 to last element. int [] a = {2,6,9}; int [] b = {7,12,15}; We have m1 < m2 Array1[] - from m1 to last element, Array2[] – from first element to m2. int [] a = {6,9}; int [] b = {7,12}; Now we have 2 elements left in both the arrays so now apply the formula Median = (max(array[0],array[0]) + min(array[1],array[1]))/2 =(max(6,7) + min(9,12))/2 = (7+9)/2 =8
Time Complexity: O(logn)
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MedianBinary { | |
public float find(int [] a, int start_a, int end_a, int [] b, int start_b, int end_b){ | |
if(end_a–start_a+1==2 && end_b–start_b+1==2){ | |
float x = Math.max(a[start_a],b[start_b]); | |
float y = Math.min(a[end_a],b[end_b]); | |
return (x+y)/2; | |
} | |
float median_a = getMedian(a, start_a, end_a); | |
float median_b = getMedian(b, start_b, end_b); | |
int mid_a = (start_a+end_a)/2; | |
int mid_b = (start_b+end_b)/2; | |
if(median_a>median_b){ | |
return find(a,start_a,mid_a,b,mid_b,end_b); | |
}else{ | |
return find(a,mid_a,end_a,b,start_b,mid_b); | |
} | |
} | |
public float getMedian(int [] x, int start, int end){ | |
int size = end–start+1; | |
double median; | |
if(size%2==0){ | |
float m = x[start+(size/2)]; | |
float n = x[start+(size–1)/2]; | |
return (m+n)/2; | |
}else{ | |
return x[start+(size–1)/2]; | |
} | |
} | |
public static void main(String[] args) { | |
MedianBinary m = new MedianBinary(); | |
int [] a = {2,6,9,10,11}; | |
int [] b = {1,5,7,12,15}; | |
float x = m.find(a,0,a.length–1,b,0,b.length–1); | |
System.out.println("Median of combined sorted array is: " + x); | |
} | |
} |
Output:
Median of combined sorted array is: 8.0