Median of two sorted arrays

PROBLEM STATEMENT

You are given two sorted arrays 'A' & 'B' of sizes 'N' & 'M'. You need to find the median of the two arrays when merged. If the total number of elements i.e., N + M is even then the median will be the mean of two medians.

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.

Follow Up

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.

Try Problem

Approach 2

The second approach is using a two-pointer approach to get middle elements.

The algorithm is as follows:

Initialize two pointers i and j to 0.
Move a pointer forward which has a smaller value.
Move the pointers until we process half the number of elements.
Then calculate the median.

Try Problem

Approach 3

The third approach is using binary search to find median.

The algorithm is as follows:

Use Binary Search to partition the smaller array in two parts.
Find the partition of the second array such that the sum of elements on the left side of the partition in both the arrays has half of the total elements.
Check if this partition is valid by verifying if the largest number of left partitions is smaller than the smallest number of the right partitions.
If the partition is valid then calculate and return the median.

Try Problem