Find median of two sorted arrays of same size

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



A = 2, 6, 9
B = 1, 5, 7
Median = (5+6)/2 = 5.5
Explanation: combined array: 1, 2, 5, 6, 7, 9


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

  1. Say arrays are array1[] and array2[].
  2. Calculate the median of both the arrays, say m1 and m2 for array1[] and array2[].
  3. If m1 == m2 then return m1 or m2 as final result.
  4. If m1 > m2 then median will be present in either of the sub arrays.
    1. Array1[] – from first element to m1.
    2. Array2[] – from m2 to last element.
  5. If m2 > m1 then median will be present in either of the sub arrays.
    1. Array1[] – from m1 to last element.
    2. Array2[] – from first element to m2.
  6. Repeat the steps from 1 to 5 recursively until 2 elements are left in both the arrays.
  7. Then apply the formula to get the median
    1. 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

Time Complexity: O(logn)



Median of combined sorted array is: 8.0

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

2 Responses

  1. Jay says:

    Hi, It doesn’t work for the input {1,3,5,7} {2,4,6,8}. Output should be 4.5. but it outputs 5.5

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: