**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 formulaMedian= (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:**

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