# Median of two sorted arrays

Posted: 25 Dec, 2020
Difficulty: Hard

## PROBLEM STATEMENT

#### Example:

``````Let array A = { 2, 4, 6, 8 } and array B = { 1, 3, 5, 7 }.
The array after merging A and B will be { 1, 2, 3, 4, 5, 6, 7, 8 }.
Here two medians are 4 & 5. So the median will be a mean of 4 & 5, which is 4.5.
``````
``````Can you solve this in O(min(log N, log M)) time complexity?
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the sizes of the two arrays.

The second line of each test case contains 'N' space-separated integers representing the elements of the first array.

The third line of each test case contains 'M' space-separated integers representing the elements of the second array.
``````
##### Output format :
``````For each test case, print a single line containing a single integer denoting the median of the combined array.

The output of each test case will be printed in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10 ^ 6
1 <= M <= 10 ^ 6
1 <= A[i] <= 10 ^ 9
1 <= B[i] <= 10 ^ 9

Time limit: 1 sec.
`````` Approach 1

The first approach is by joining the array and again sorting is to get median.

The algorithm is as follows:

• Create a new array of size of total number of elements.
• Insert elements of both the arrays in the array.
• Sort the array and find the median.