# Median of two sorted arrays

Posted: 25 Dec, 2020

Difficulty: Hard

#### 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

Approach 2

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.

SIMILAR PROBLEMS

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy