## Median of Two Sorted Arrays of Same Size

Before getting into the problem statement of finding the median of two sorted arrays, let us first get a brief introduction about the arrays.

An array is a linear collection of values stored at contiguous memory locations. Array stores homogeneous values(similar data type values).

To learn more about the arrays, refer to the article – Arrays in Data Structure.

**Note:**

A list is used to store one or more objects or data elements. Lists are used in python and java mostly. We can say that lists are similar to arrays.

Median is the mid element (`middle element`

) of an `sorted array`

if the number of elements in the array is odd. If the number of elements in the array is even then the median is the average of the two middle elements.

### Problem Statement

We are provided with two sorted arrays named array_1 and array_2 of size n each and we need to find the median of the array obtained after merging the provided two sorted arrays.

- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.

### Constraints

- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $

Here, $ m == n $ as both the arrays are of same length.

In some problems, you may find the number of test cases represented by `t`

. So, we only need to call the `findMedian`

function `t`

-times.

The problem is to find the median of two sorted arrays.

### Example

Let us look at some of the examples provided to find the median of two sorted arrays of same length.

**Example 1:**

Given, first input array is `[ 1, 12, 15, 26, 38 ]`

Given, second input array is `[ 2, 13, 17, 30, 45 ]`

**Output:**

`The median of two sorted arrays is 16.0`

**Example 2:**

Given, first input the array is `[ 1, 2 ]`

Given, second input array is `[ 3, 4 ]`

**Output:**

`The median of two sorted arrays is 2 (floor value of 2.5 is 2)`

### Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ 1, 12, 15, 26, 38 ]

The second array (a2) is [ 2, 13, 17, 30, 45 ]

After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]

The average of the two middle elements is:$ (15 + 17)/2 $ i.e. `16`

.**Note**: The size of the first array is `n`

then the size of the merged array is `2n`

and hence we need to take the average of the two middle elements.

### Approach 1: Simply Count While Merging

The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.

We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.

Since there can be `2n`

elements in the array, whenever our counter reaches `n`

, it means we have reached the median of the two arrays. We just need to take the average of the `n`

th element and `n+1`

th element as the size of the merged array is even.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
```

**Implementation:**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point to the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n
**
** when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point the
** the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

```
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
```

**Output**:

```
The median of two sorted arrays is: 16
```

**Complexity Analysis**

In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.

**Time Complexity**

As we are traversing only the first n elements of the arrays, the time complexity is **O(n)**.

**Space Complexity**

We are not using any extra space rather than a count variable. So, space complexity is **O(1)**.

### Approach 2: By Comparing the Medians of Two Arrays

In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function for finding median of array*
int median(int a[], int n) {
*// checking if length is even or odd*
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
*// base cases *
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
*// median of the first array*
int m1 = median(a1, n);
*// median of the second array*
int m2 = median(a2, n);
if (m1 == m2)
return m1;
*// if the first median is smaller then check further*
if (m1 < m2) {
*// if the length of the array is even, recursively call the function*
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
```*// a function for finding median of array*
static int median(int[] a, int start, int end) {
int n = end - start + 1;
*// checking if length is even or odd*
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
*// a recursive function that returns the median of the array*
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
*// base case*
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
*// median of the first array*
int m1 = median(a1, start_a1, end_a1);
*// median of the second array*
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
*// if the median of the first array is smaller then recursively call the function*
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}

**Python code:**

*# a function for finding median of array*
def median(a, n):
*# checking if length is even or odd*
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
*# a recursive function that returns the median of the array*
def findMedian(a1, a2, n):
*# base cases*
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
*# median of the first array*
m1 = median(a1, n)
*# median of the second array*
m2 = median(a2, n)
*# if first median is larger then check further*
if m1 > m2:
*# if the length of array is even*
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
*# if first median is smaller then check further*
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.

**Time Complexity**

So, the time complexity is **O(log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

### Approach 3: By Taking Union w/o Extra Space

In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function that returns the median of the array.*
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
*// sorting both the arrays *
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
import java.util.*;
public class Test {
```*// a function that returns the median of the array.*
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1) {
*// swapping*
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
*// sorting both the arrays *
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

*# a function that returns the median of the array.*
def findMedian(a1, a2, n):
i, j = n - 1, 0
*# union of both the arrays*
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
*# sorting both the arrays *
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.

**Time Complexity**

So, the time complexity is **O(n log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

## Median of Two Sorted Arrays of Different Sizes

So far we have seen the approaches of finding the median of two sorted arrays of the same length.

Let us now discuss a variance of this problem where the size of both the arrays is not the same.

### Problem Statement

We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.

- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.

### Constraints

- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $

Here, $ m == n $ as both the arrays are of same length.

In some problems, you may find the number of test cases represented by `t`

. So, we only need to call the `findMedian`

function `t`

-times.

The problem is to find the median of two sorted arrays.

### Example

Let us look at some of the examples provided to find the median of two sorted arrays of same length.

**Example 1:**

Given, first input array is `[ 1, 12, 15, 26, 38 ]`

Given, second input array is `[ 2, 13, 17, 30, 45 ]`

**Output:**

`The median of two sorted arrays is 16.0`

**Example 2:**

Given, first input the array is `[ 1, 2 ]`

Given, second input array is `[ 3, 4 ]`

**Output:**

`The median of two sorted arrays is 2 (floor value of 2.5 is 2)`

### Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ 1, 12, 15, 26, 38 ]

The second array (a2) is [ 2, 13, 17, 30, 45 ]

After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]

The average of the two middle elements is:$ (15 + 17)/2 $ i.e. `16`

.**Note**: The size of the first array is `n`

then the size of the merged array is `2n`

and hence we need to take the average of the two middle elements.

### Approach 1: Simply Count While Merging

The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.

We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.

Since there can be `2n`

elements in the array, whenever our counter reaches `n`

, it means we have reached the median of the two arrays. We just need to take the average of the `n`

th element and `n+1`

th element as the size of the merged array is even.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
```

**Implementation:**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point to the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n
**
** when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point the
** the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

```
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
```

**Output**:

```
The median of two sorted arrays is: 16
```

**Complexity Analysis**

In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.

**Time Complexity**

As we are traversing only the first n elements of the arrays, the time complexity is **O(n)**.

**Space Complexity**

We are not using any extra space rather than a count variable. So, space complexity is **O(1)**.

### Approach 2: By Comparing the Medians of Two Arrays

In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function for finding median of array*
int median(int a[], int n) {
*// checking if length is even or odd*
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
*// base cases *
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
*// median of the first array*
int m1 = median(a1, n);
*// median of the second array*
int m2 = median(a2, n);
if (m1 == m2)
return m1;
*// if the first median is smaller then check further*
if (m1 < m2) {
*// if the length of the array is even, recursively call the function*
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
```*// a function for finding median of array*
static int median(int[] a, int start, int end) {
int n = end - start + 1;
*// checking if length is even or odd*
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
*// a recursive function that returns the median of the array*
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
*// base case*
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
*// median of the first array*
int m1 = median(a1, start_a1, end_a1);
*// median of the second array*
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
*// if the median of the first array is smaller then recursively call the function*
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}

**Python code:**

*# a function for finding median of array*
def median(a, n):
*# checking if length is even or odd*
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
*# a recursive function that returns the median of the array*
def findMedian(a1, a2, n):
*# base cases*
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
*# median of the first array*
m1 = median(a1, n)
*# median of the second array*
m2 = median(a2, n)
*# if first median is larger then check further*
if m1 > m2:
*# if the length of array is even*
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
*# if first median is smaller then check further*
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.

**Time Complexity**

So, the time complexity is **O(log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

### Approach 3: By Taking Union w/o Extra Space

In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function that returns the median of the array.*
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
*// sorting both the arrays *
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
import java.util.*;
public class Test {
```*// a function that returns the median of the array.*
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1) {
*// swapping*
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
*// sorting both the arrays *
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

*# a function that returns the median of the array.*
def findMedian(a1, a2, n):
i, j = n - 1, 0
*# union of both the arrays*
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
*# sorting both the arrays *
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.

**Time Complexity**

So, the time complexity is **O(n log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

## Median of Two Sorted Arrays of Different Sizes

So far we have seen the approaches of finding the median of two sorted arrays of the same length.

Let us now discuss a variance of this problem where the size of both the arrays is not the same.

### Problem Statement

We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.

- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.

### Constraints

- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $

Here, $ m == n $ as both the arrays are of same length.

In some problems, you may find the number of test cases represented by `t`

. So, we only need to call the `findMedian`

function `t`

-times.

The problem is to find the median of two sorted arrays.

### Example

Let us look at some of the examples provided to find the median of two sorted arrays of same length.

**Example 1:**

Given, first input array is `[ 1, 12, 15, 26, 38 ]`

Given, second input array is `[ 2, 13, 17, 30, 45 ]`

**Output:**

`The median of two sorted arrays is 16.0`

**Example 2:**

Given, first input the array is `[ 1, 2 ]`

Given, second input array is `[ 3, 4 ]`

**Output:**

`The median of two sorted arrays is 2 (floor value of 2.5 is 2)`

### Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ 1, 12, 15, 26, 38 ]

The second array (a2) is [ 2, 13, 17, 30, 45 ]

After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]

The average of the two middle elements is:$ (15 + 17)/2 $ i.e. `16`

.

:::section{.tip}**Note**: The size of the first array is `n`

then the size of the merged array is `2n`

and hence we need to take the average of the two middle elements.

### Approach 1: Simply Count While Merging

The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.

We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.

Since there can be `2n`

elements in the array, whenever our counter reaches `n`

, it means we have reached the median of the two arrays. We just need to take the average of the `n`

th element and `n+1`

th element as the size of the merged array is even.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
```

**Implementation:**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point to the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n
**
** when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point the
** the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

```
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
```

**Output**:

```
The median of two sorted arrays is: 16
```

**Complexity Analysis**

In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.

**Time Complexity**

As we are traversing only the first n elements of the arrays, the time complexity is **O(n)**.

**Space Complexity**

We are not using any extra space rather than a count variable. So, space complexity is **O(1)**.

### Approach 2: By Comparing the Medians of Two Arrays

In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function for finding median of array*
int median(int a[], int n) {
*// checking if length is even or odd*
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
*// base cases *
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
*// median of the first array*
int m1 = median(a1, n);
*// median of the second array*
int m2 = median(a2, n);
if (m1 == m2)
return m1;
*// if the first median is smaller then check further*
if (m1 < m2) {
*// if the length of the array is even, recursively call the function*
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
```*// a function for finding median of array*
static int median(int[] a, int start, int end) {
int n = end - start + 1;
*// checking if length is even or odd*
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
*// a recursive function that returns the median of the array*
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
*// base case*
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
*// median of the first array*
int m1 = median(a1, start_a1, end_a1);
*// median of the second array*
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
*// if the median of the first array is smaller then recursively call the function*
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}

**Python code:**

*# a function for finding median of array*
def median(a, n):
*# checking if length is even or odd*
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
*# a recursive function that returns the median of the array*
def findMedian(a1, a2, n):
*# base cases*
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
*# median of the first array*
m1 = median(a1, n)
*# median of the second array*
m2 = median(a2, n)
*# if first median is larger then check further*
if m1 > m2:
*# if the length of array is even*
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
*# if first median is smaller then check further*
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.

**Time Complexity**

So, the time complexity is **O(log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

### Approach 3: By Taking Union w/o Extra Space

In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function that returns the median of the array.*
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
*// sorting both the arrays *
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
import java.util.*;
public class Test {
```*// a function that returns the median of the array.*
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1) {
*// swapping*
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
*// sorting both the arrays *
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

*# a function that returns the median of the array.*
def findMedian(a1, a2, n):
i, j = n - 1, 0
*# union of both the arrays*
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
*# sorting both the arrays *
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.

**Time Complexity**

So, the time complexity is **O(n log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

## Median of Two Sorted Arrays of Different Sizes

So far we have seen the approaches of finding the median of two sorted arrays of the same length.

Let us now discuss a variance of this problem where the size of both the arrays is not the same.

### Problem Statement

We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.

- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.

### Constraints

- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $

Here, $ m == n $ as both the arrays are of same length.

`t`

. So, we only need to call the `findMedian`

function `t`

-times.

The problem is to find the median of two sorted arrays.

### Example

Let us look at some of the examples provided to find the median of two sorted arrays of same length.

**Example 1:**

Given, first input array is `[ 1, 12, 15, 26, 38 ]`

Given, second input array is `[ 2, 13, 17, 30, 45 ]`

**Output:**

`The median of two sorted arrays is 16.0`

**Example 2:**

Given, first input the array is `[ 1, 2 ]`

Given, second input array is `[ 3, 4 ]`

**Output:**

`The median of two sorted arrays is 2 (floor value of 2.5 is 2)`

### Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ 1, 12, 15, 26, 38 ]

The second array (a2) is [ 2, 13, 17, 30, 45 ]

After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]

The average of the two middle elements is:$ (15 + 17)/2 $ i.e. `16`

.

:::section{.tip}**Note**: The size of the first array is `n`

then the size of the merged array is `2n`

and hence we need to take the average of the two middle elements.

### Approach 1: Simply Count While Merging

`2n`

elements in the array, whenever our counter reaches `n`

, it means we have reached the median of the two arrays. We just need to take the average of the `n`

th element and `n+1`

th element as the size of the merged array is even.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Initialize a counter variable with 0.
2. Traverse the array and when the counter reaches half the size of the merged array i.e. n, stop the counter.
3. Finally return the average of the element present at the index n-1 and n in the array.
```

**Implementation:**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point to the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n
**
** when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
}
else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
int main() {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
static int findMedian(int a1[],
int a2[], int n) {
```*/*
** i will point to the current index of the first array and j will point the
** the current index of the second array
** */*
int i = 0;
int j = 0;
*/*
** a counter that counts the elements till the counter reaches n when the counter reaches n elements it means we have reached the median of the two arrays
** */*
int count;
int firstMedian = -1, secondMedian = -1;
for (count = 0; count <= n; count++) {
*/*
** when all elements of a1[] are smaller than smallest than the first element of a2[]
** */*
if (i == n) {
firstMedian = secondMedian;
secondMedian = a2[0];
break;
}
*/*
** when all elements of a2[] are smaller than smallest than the first element of a1[]
** */*
else if (j == n) {
firstMedian = secondMedian;
secondMedian = a1[0];
break;
}
if (a1[i] <= a2[j]) {
firstMedian = secondMedian;
secondMedian = a1[i];
i++;
} else {
firstMedian = secondMedian;
secondMedian = a2[j];
j++;
}
}
return (firstMedian + secondMedian) / 2;
}
public static void main(String args[]) {
int a1[] = {1, 12, 15, 26, 38};
int a2[] = {2, 13, 17, 30, 45};
System.out.println("The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

```
def findMedian(a1, a2, n):
"""
i will point to the current index of the first array and j will point to the current index of the second array
"""
i = 0
j = 0
firstMedian = -1
secondMedian = -1
"""
a counter that counts the elements till the counter reaches n
when the counter reaches n elements it means we have reached the median of the two arrays (lists)
"""
count = 0
while count < n + 1:
count += 1
"""
when all elements of a1[] are smaller than smallest than the first element of a2[]
the else parts:
when all elements of a2[] are smaller than smallest than the first element of a1[]
"""
if i == n:
firstMedian = secondMedian
secondMedian = a2[0]
break
elif j == n:
firstMedian = secondMedian
secondMedian = a1[0]
break
if a1[i] <= a2[j]:
firstMedian = secondMedian
secondMedian = a1[i]
i += 1
else:
firstMedian = secondMedian
secondMedian = a2[j]
j += 1
return int((firstMedian + secondMedian)/2)
if __name__ == '__main__':
a1 = [1, 12, 15, 26, 38]
a2 = [2, 13, 17, 30, 45]
print("The median of two sorted arrays is: ", findMedian(a1, a2, len(a1)))
```

**Output**:

```
The median of two sorted arrays is: 16
```

**Complexity Analysis**

**Time Complexity**

As we are traversing only the first n elements of the arrays, the time complexity is **O(n)**.

**Space Complexity**

We are not using any extra space rather than a count variable. So, space complexity is **O(1)**.

### Approach 2: By Comparing the Medians of Two Arrays

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. First calculate the median of both the arrays i.e. a1 (firstMedian), and a2 (secondMedian).
2. If both the firstMedian and the secondMedian are equal then we have found our answer. So, return either firstMedian or secondMedian as the answer.
3. If the firstMedian is greater than the secondMedian then the required median must lie in the sub-arrays:
- from the first element of a1 to the firstMedian.
- or from the secondMedian to the last element of a2.
4. If the firstMedian is smaller than the secondMedian then the required median must lie in the sub-arrays:
- from the firstMedian to the last element of a1.
- or from the first element of a2 to the secondMedian.
5. Repeat the process until the size of the sub-arrays becomes 2.
If the size of the sub arrays becomes 2, then median is:
Median = (max(a1[0], a2[0]) + min(a1[1], a2[1]))/2
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function for finding median of array*
int median(int a[], int n) {
*// checking if length is even or odd*
if (n % 2 == 0)
return (a[n / 2] + a[n / 2 - 1]) / 2;
else
return a[n / 2];
}
int findMedian(int a1[],
int a2[], int n) {
*// base cases *
if (n <= 0)
return -1;
if (n == 1)
return (a1[0] + a2[0]) / 2;
if (n == 2)
return (max(a1[0], a2[0]) + min(a1[1], a2[1])) / 2;
*// median of the first array*
int m1 = median(a1, n);
*// median of the second array*
int m2 = median(a2, n);
if (m1 == m2)
return m1;
*// if the first median is smaller then check further*
if (m1 < m2) {
*// if the length of the array is even, recursively call the function*
if (n % 2 == 0)
return findMedian(a1 + n / 2 - 1,
a2, n - n / 2 + 1);
return findMedian(a1 + n / 2,
a2, n - n / 2);
}
if (n % 2 == 0)
return findMedian(a2 + n / 2 - 1,
a1, n - n / 2 + 1);
return findMedian(a2 + n / 2,
a1, n - n / 2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
public class Test {
```*// a function for finding median of array*
static int median(int[] a, int start, int end) {
int n = end - start + 1;
*// checking if length is even or odd*
if (n % 2 == 0) {
return (a[start + (n / 2)]
+ a[start + (n / 2 - 1)])
/ 2;
} else {
return a[start + n / 2];
}
}
*// a recursive function that returns the median of the array*
static int findMedian(int[] a1, int[] a2, int start_a1,
int start_a2, int end_a1, int end_a2) {
*// base case*
if (end_a1 - start_a1 == 1) {
return (Math.max(a1[start_a1],
a2[start_a2])
+ Math.min(a1[end_a1], a2[end_a2]))
/ 2;
}
*// median of the first array*
int m1 = median(a1, start_a1, end_a1);
*// median of the second array*
int m2 = median(a2, start_a2, end_a2);
if (m1 == m2) {
return m1;
}
*// if the median of the first array is smaller then recursively call the function*
else if (m1 < m2) {
return findMedian(
a1, a2, (end_a1 + start_a1 + 1) / 2,
start_a2, end_a1,
(end_a2 + start_a2 + 1) / 2);
}
else {
return findMedian(
a1, a2, start_a1,
(end_a2 + start_a2 + 1) / 2,
(end_a1 + start_a1 + 1) / 2, end_a2);
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, 0, 0, a1.length - 1, a2.length - 1));
}
}

**Python code:**

*# a function for finding median of array*
def median(a, n):
*# checking if length is even or odd*
if n % 2 == 0:
return (a[int(n / 2)] +
a[int(n / 2) - 1]) / 2
else:
return a[int(n/2)]
*# a recursive function that returns the median of the array*
def findMedian(a1, a2, n):
*# base cases*
if n == 0:
return -1
elif n == 1:
return (a1[0]+a2[0])/2
elif n == 2:
return (max(a1[0], a2[0]) +
min(a1[1], a2[1])) / 2
else:
*# median of the first array*
m1 = median(a1, n)
*# median of the second array*
m2 = median(a2, n)
*# if first median is larger then check further*
if m1 > m2:
*# if the length of array is even*
if n % 2 == 0:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2) - 1:], int(n / 2) + 1)
else:
return findMedian(a1[:int(n / 2) + 1],
a2[int(n / 2):], int(n / 2) + 1)
*# if first median is smaller then check further*
else:
if n % 2 == 0:
return findMedian(a1[int(n / 2 - 1):],
a2[:int(n / 2 + 1)], int(n / 2) + 1)
else:
return findMedian(a1[int(n / 2):],
a2[0:int(n / 2) + 1], int(n / 2) + 1)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

**Time Complexity**

So, the time complexity is **O(log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

### Approach 3: By Taking Union w/o Extra Space

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Find the union of both the input arrays.
2. Sort both the arrays respectively.
3. Find the median by the formula:
Median = [(a1[n-1] + a2[0])/2], where n is the length of the array.
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function that returns the median of the array.*
int findMedian(int a1[], int a2[], int n) {
int i = n - 1, j = 0;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1)
swap(a1[i--], a2[j++]);
*// sorting both the arrays *
sort(a1, a1 + n);
sort(a2, a2 + n);
return (a1[n - 1] + a2[0]) / 2;
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 6, 8, 10};
int n1 = sizeof(a1) /
sizeof(a1[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1);
return 0;
}

**Java code:**

```
import java.util.*;
public class Test {
```*// a function that returns the median of the array.*
static int findMedian(int a1[], int a2[], int n) {
int j = 0;
int i = n - 1;
*// union of both the arrays*
while (a1[i] > a2[j] && j < n && i > -1) {
*// swapping*
int temp = a1[i];
a1[i] = a2[j];
a2[j] = temp;
i--;
j++;
}
*// sorting both the arrays *
Arrays.sort(a1);
Arrays.sort(a2);
return (a1[n - 1] + a2[0]) / 2;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 6, 8, 10 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length));
}
}

**Python code:**

*# a function that returns the median of the array.*
def findMedian(a1, a2, n):
i, j = n - 1, 0
*# union of both the arrays*
while(a1[i] > a2[j]) and (i > -1 and j < n):
a1[i], a2[j] = a2[j], a1[i]
i -= 1
j += 1
*# sorting both the arrays *
a1.sort()
a2.sort()
return (a1[-1] + a2[0]) >> 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 6, 8, 10]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1))))

**Output:**

```
The median of two sorted arrays is: 5
```

**Complexity Analysis**

**Time Complexity**

So, the time complexity is **O(n log n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

## Median of Two Sorted Arrays of Different Sizes

So far we have seen the approaches of finding the median of two sorted arrays of the same length.

Let us now discuss a variance of this problem where the size of both the arrays is not the same.

### Problem Statement

- The first input is the sequential set of elements of the first array.
- The second input is the sequential set of elements of the second array.

### Constraints

- $ array_1.length == m $
- $ array_2.length == n $
- $ 0 <= m <= 1000 $
- $ 0 <= n <= 1000 $
- $ 1 <= m + n <= 2000 $
- $ -10^6 <= array_1[i], array_2[i] <= 10^6 $

In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.

The problem is to find the median of two sorted arrays of different lengths.

### Example

Let us look at some of the examples provided to find the second largest element in the array.

**Example 1:** Given first input array is [ -5, 3, 6, 12, 15 ] Given second input array is [ -12, -10, -6, -3, 4, 10 ] **Output:**

```
The median of two sorted arrays is 3
```

**Example 2:** Given the first input, array is [ 2, 3, 5, 8 ] Given second input array is [ 10, 12, 14, 16, 18, 20 ]

**Output:**

```
The median of two sorted arrays is 11
```

### Example Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ -5, 3, 6, 12, 15 ] The second array (a2) is [ -12, -10, -6, -3, 4, 10 ]

After merging these two arrays, the merged array is [ -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 ]

The median of the array is 3 as the size of the merged array is 11 so the median is present at the 5th index i.e. 11/2 (floor value comes out to be 5).

### Approach 1: Linear and Simpler Approach

The size of the merged array can be even or odd. Let us see both the cases:

- If the size of the array is odd (i.e. m+n
*m*+*n*is odd) then median is obtained as (m+n)/2(*m*+*n*)/2. - If the size of the array is even (i.e. m + n is even) then the median is obtained as the average of (m+n)/2−1(
*m*+*n*)/2−1 and (m+n)/2(*m*+*n*)/2.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Merge the two input arrays and initialize a counter variable.
2. Take two variables i, and j. i points to the starting index of the first array and j points to the starting index of the second array.
3. If the size of the array is odd then:
- Traverse the array and when the counter reaches (m + n)/2, stop the counter and return the result as a[(m + n)/2].
4. Else:
- Traverse the array and when the counter reaches (m + n)/2, stop the counter and return the result as the average of elements at index (m+n)/2 and ((m+n)/2 – 1).
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function to return the median of the array*
int findMedian(int a1[], int a2[], int n, int m) {
*/*
** i points to the starting index of the first array and j points to the starting index of the second array.
** */*
int i = 0;
int j = 0;
int count;
int firstMedian = -1, secondMedian = -1;
*// If the size of the array is odd then traverse the array and when the counter reaches (m + n)/2.*
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
}
else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return firstMedian;
}
*// otherwise, traverse the array and when the counter reaches (m + n)/2.*
else {
for (count = 0; count <= (n + m) / 2; count++) {
secondMedian = firstMedian;
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
}
else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return (firstMedian + secondMedian) / 2;
}
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1, n2);
return 0;
}

**Java code:**

```
public class Test {
```*// a function to return the median of the array*
static int findMedian(int a1[], int a2[], int n, int m) {
*/*
** i points to the starting index of the first array and j points to the starting index of the second array.
** */*
int i = 0;
int j = 0;
int count;
int firstMedian = -1, secondMedian = -1;
*// If the size of the array is odd then traverse the array and when the counter reaches (m + n)/2.*
if ((m + n) % 2 == 1) {
for (count = 0; count <= (n + m) / 2; count++) {
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
} else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return firstMedian;
}
*// otherwise, traverse the array and when the counter reaches (m + n)/2.*
else {
for (count = 0; count <= (n + m) / 2; count++) {
secondMedian = firstMedian;
if (i != n && j != m) {
firstMedian = (a1[i] > a2[j]) ? a2[j++] : a1[i++];
} else if (i < n) {
firstMedian = a1[i++];
}
else {
firstMedian = a2[j++];
}
}
return (firstMedian + secondMedian) / 2;
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length, a2.length));
}
}

**Python code:**

*# a function to return the median of the array*
def findMedian(a1, a2, n, m):
"""
i points to the starting index of the first array and j points to the starting index of the second array.
"""
i = 0
j = 0
firstMedian, secondMedian = -1, -1
*# If the size of the array is odd then traverse the array and when the counter reaches (m + n)/2.*
if((m + n) % 2 == 1):
for count in range(((n + m) // 2) + 1):
if(i != n and j != m):
if a1[i] > a2[j]:
firstMedian = a2[j]
j += 1
else:
firstMedian = a1[i]
i += 1
elif(i < n):
firstMedian = a1[i]
i += 1
else:
firstMedian = a2[j]
j += 1
return firstMedian
*# otherwise, traverse the array and when the counter reaches (m + n)/2.*
else:
for count in range(((n + m) // 2) + 1):
secondMedian = firstMedian
if(i != n and j != m):
if a1[i] > a2[j]:
firstMedian = a2[j]
j += 1
else:
firstMedian = a1[i]
i += 1
elif(i < n):
firstMedian = a1[i]
i += 1
else:
firstMedian = a2[j]
j += 1
return (firstMedian + secondMedian)//2
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
print("The median of two sorted arrays is: ",
int(findMedian(a1, a2, len(a1), len(a2))))

**Output:**

```
The median of two sorted arrays is: 6
```

**Complexity Analysis**

In this basic approach to finding the median of two sorted arrays of different lengths, we have traversed the arrays and counted the first m + n sorted elements of the merged array.

**Time Complexity**

As we are traversing only the first m + n elements of the arrays, the time complexity is **O(m + n)**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

### Approach 2: Efficient Solution

An efficient approach of finding the median of two sorted arrays of varying sizes can be finding the median of both the arrays and then discarding the one half (sub-array) of both the arrays. Let us see the algorithm and code for a better understanding.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Create a recursive function that takes both arrays.
2. Find the median of both the arrays and compare them.
3. If the median of the smaller array is lesser than the median of the larger array then we discard the first half of smaller array & second half of the larger array and vice versa.
4. Repeat the procedure by dividing the array into smaller sub-arrays and finally returning the result.
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// A function that returns the median of two integers*
float medianOfTwo(int a, int b) {
return (a + b) / 2.0;
}
*// A function that returns the median of three integers*
float medianOfThree(int a, int b, int c) {
return a + b + c - max(a, max(b, c)) - min(a, min(b, c));
}
*// A function that returns the median of four integers*
float medianOfFour(int a, int b, int c, int d) {
int MAX = max(a, max(b, max(c, d)));
int MIN = min(a, min(b, min(c, d)));
return (a + b + c + d - MAX - MIN) / 2.0;
}
*// A function that returns the median of an array*
float medianSingle(int a[], int n) {
if (n == 0)
return -1;
if (n % 2 == 0)
return (double)(a[n / 2] + a[n / 2 - 1]) / 2;
return a[n / 2];
}
*// A utility function that deals with the case when n1 is smaller than or equal to n2.*
float findMedianUtil(int A[], int n1, int B[], int n2) {
*// When the smaller array is empty*
if (n1 == 0)
return medianSingle(B, n2);
*// When the smaller array has only one element*
if (n1 == 1) {
*// Case 1: When the larger array has only one element*
if (n2 == 1)
return medianOfTwo(A[0], B[0]);
*// Case 2: When the larger array has odd number of elements*
if (n2 & 1)
return medianOfTwo(B[n2 / 2], medianOfThree(A[0], B[n2 / 2 - 1], B[n2 / 2 + 1]));
*// Case 3: When the larger array has even number of elements*
return medianOfThree(B[n2 / 2], B[n2 / 2 - 1], A[0]);
}
*// When the smaller array has two elements*
else if (n1 == 2) {
*// Case 4: When the larger array has two elements*
if (n2 == 2)
return medianOfFour(A[0], A[1], B[0], B[1]);
*// Case 5: When the larger array has odd number of elements*
if (n2 & 1)
return medianOfThree(B[n2 / 2],
max(A[0], B[n2 / 2 - 1]),
min(A[1], B[n2 / 2 + 1]));
*// Case 6: When the larger array has even number of elements*
return medianOfFour(B[n2 / 2],
B[n2 / 2 - 1],
max(A[0], B[n2 / 2 - 2]),
min(A[1], B[n2 / 2 + 1]));
}
int indexA = (n1 - 1) / 2;
int indexB = (n2 - 1) / 2;
if (A[indexA] <= B[indexB])
return findMedianUtil(A + indexA, n1 / 2 + 1, B, n2 - indexA);
return findMedianUtil(A, n1 / 2 + 1, B + indexA, n2 - indexA);
}
float findMedian(int A[], int B[], int n1, int n2) {
if (n1 > n2)
return findMedianUtil(B, n2, A, n1);
return findMedianUtil(A, n1, B, n2);
}
int main() {
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2, n1, n2);
return 0;
}

**Java code:**

```
import java.util.*;
public class Test {
static double medianOfTwo(double a, double b) {
return (a + b) / 2.0;
}
```*// A function that returns the median of three integers*
static double medianOfThree(double a, double b, double c) {
return a + b + c - Math.max(a, Math.max(b, c)) - Math.min(a, Math.min(b, c));
}
*// A function that returns the median of four integers*
static double medianOfFour(int a, int b, int c, int d) {
int MAX = Math.max(a, Math.max(b, Math.max(c, d)));
int MIN = Math.min(a, Math.min(b, Math.min(c, d)));
return (a + b + c + d - MAX - MIN) / 2.0;
}
*// A function that returns the median of an array*
static double medianSingle(int a[], int n) {
if (n == 0)
return -1;
if (n % 2 == 0)
return (double) (a[n / 2] + a[n / 2 - 1]) / 2;
return a[n / 2];
}
*// A utility function that deals with the case when n1 is smaller than or equal*
*// to n2.*
static double findMedianUtil(int A[], int n1, int B[], int n2) {
*// When the smaller array is empty*
if (n1 == 0)
return medianSingle(B, n2);
*// When the smaller array has only one element*
if (n1 == 1) {
*// Case 1: When the larger array has only one element*
if (n2 == 1)
return medianOfTwo(A[0], B[0]);
*// Case 2: When the larger array has odd number of elements*
if (n2 % 2 != 0)
return medianOfTwo(B[n2 / 2], medianOfThree(A[0], B[n2 / 2 - 1], B[n2 / 2 + 1]));
*// Case 3: When the larger array has even number of elements*
return medianOfThree(B[n2 / 2], B[n2 / 2 - 1], A[0]);
}
*// When the smaller array has two elements*
else if (n1 == 2) {
*// Case 4: When the larger array has two elements*
if (n2 == 2)
return medianOfFour(A[0], A[1], B[0], B[1]);
*// Case 5: When the larger array has odd number of elements*
if (n2 % 2 != 0)
return medianOfThree(B[n2 / 2],
Math.max(A[0], B[n2 / 2 - 1]),
Math.min(A[1], B[n2 / 2 + 1]));
*// Case 6: When the larger array has even number of elements*
return medianOfFour(B[n2 / 2],
B[n2 / 2 - 1],
Math.max(A[0], B[n2 / 2 - 2]),
Math.min(A[1], B[n2 / 2 + 1]));
}
int indexA = (n1 - 1) / 2;
int indexB = (n2 - 1) / 2;
if (A[indexA] <= B[indexB])
return findMedianUtil(Arrays.copyOfRange(A, indexA, A.length), n1 / 2 + 1, B, n2 - indexA);
return findMedianUtil(A, n1 / 2 + 1, Arrays.copyOfRange(B, indexB, B.length), n2 - indexA);
}
static double findMedian(int A[], int B[], int n1, int n2) {
if (n1 > n2)
return findMedianUtil(B, n2, A, n1);
return findMedianUtil(A, n1, B, n2);
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2, a1.length, a2.length));
}
}

**Python code:**

*# A function that returns the median of two integers*
def medianOfTwo(a, b):
return (a + b) / 2
*# A utility function to find median of three integers*
def medianOfThree(a, b, c):
return a + b + c - max(a, max(b, c)) - min(a, min(b, c))
*# A utility function to find a median of four integers*
def medianOfFour(a, b, c, d):
MAX = max(a, max(b, max(c, d)))
MIN = min(a, min(b, min(c, d)))
return (a + b + c + d - MAX - MIN) / 2
*# A function that returns the median of an array*
def medianSingle(a, n):
if (n == 0):
return -1
if (n % 2 == 0):
return (a[n // 2] + a[n // 2 - 1]) / 2
return a[n // 2]
*# A utility function that deals with the case when n1 is smaller than or equal to n2.*
def findMedianUtil(A, n1, B, n2):
*# When the smaller array is empty*
if (n1 == 0):
return medianSingle(B, n2)
*# When the smaller array has only one element*
if (n1 == 1):
*# Case 1: When the larger array has only one element*
if (n2 == 1):
return medianOfTwo(A[0], B[0])
*# Case 2: When the larger array has odd number of elements*
if (n2 & 1 != 0):
return medianOfTwo(B[n2 // 2], medianOfThree(A[0], B[n2 // 2 - 1], B[n2 // 2 + 1]))
*# Case 3: When the larger array has even number of elements*
return medianOfThree(B[n2 // 2], B[n2 // 2 - 1], A[0])
*# When the smaller array has two elements*
elif (n1 == 2):
*# Case 4: When the larger array has two elements*
if (n2 == 2):
return medianOfFour(A[0], A[1], B[0], B[1])
*# Case 5: When the larger array has odd number of elements*
if (n2 & 1 != 0):
return medianOfThree(B[n2 // 2], max(A[0], B[n2 // 2 - 1]), min(A[1], B[n2 // 2 + 1]))
*# Case 6: When the larger array has even number of elements*
return medianOfFour(B[n2 // 2], B[n2 // 2 - 1], max(A[0], B[n2 // 2 - 2]), min(A[1], B[n2 // 2 + 1]))
indexA = (n1 - 1) // 2
indexB = (n2 - 1) // 2
if (A[int(indexA)] <= B[int(indexB)]):
return findMedianUtil(A + indexA, n1 // 2 + 1, B, n2 - indexA)
return findMedianUtil(A, n1 // 2 + 1, B + indexA, n2 - indexA)
def findMedian(A, n1, B, n2):
if n1 > n2:
return findMedianUtil(B, n2, A, n1)
return findMedianUtil(A, n1, B, n2)
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
print("The median of two sorted arrays is: ",
int(findMedian(a1, len(a1), a2, len(a2))))

**Output:**

```
The median of two sorted arrays is: 6
```

**Complexity Analysis**

In this approach to finding the median of two sorted arrays of different lengths, we have used the divide and conquer technique as in each step, we are discarding one-half of the array.

**Time Complexity**

So, the time complexity is **O(min(log m, log n))**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

### Approach 3: Simple Mathematical Approach

In this approach of finding the median of two sorted arrays can be merging the two arrays into a single array and then sorting the resulting array. Now depending upon the size of the resultant array, we can easily find the median and return it.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Merge the two arrays into a single array.
2. Sort the resulting array.
3. If the size of the resulting array is odd:
return a[length/2]
Else:
return (a[length/2] + a[(length/2) - 1]) / 2
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
int findMedian(int a[], int n) {
```*// When length of array is even*
if (n % 2 == 0) {
int z = n / 2;
int e = a[z];
int q = a[z - 1];
int result = (e + q) / 2;
return result;
}
*// When the length of the array is odd*
else {
int z = round(n / 2);
return a[z];
}
}
int main()
{
int a1[] = {1, 2, 3, 6};
int a2[] = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
int n = n1 + n2;
int a3[n];
*// merging both the arrays*
for (int i = 0; i < n1; i++)
a3[i] = a1[i];
int j = 0;
for (int i = n1; i < n; i++)
a3[i] = a2[j++];
*// Sorting the merged arrays*
sort(a3, a3 + n);
cout << "The median of two sorted arrays is: " << findMedian(a3, n);
return 0;
}

**Java code:**

```
import java.util.*;
public class Test {
static int findMedian(int a[], int n) {
```*// When length of array is even*
if (n % 2 == 0) {
int z = n / 2;
int e = a[z];
int q = a[z - 1];
int result = (e + q) / 2;
return result;
}
*// When length of array is odd*
else {
int z = Math.round(n / 2);
return a[z];
}
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
int n1 = a1.length;
int n2 = a2.length;
int n = n1 + n2;
int a3[] = new int[n];
*// merging both the arrays*
System.arraycopy(a1, 0, a3, 0, n1);
System.arraycopy(a2, 0, a3, n1, n2);
*// Sorting the merged arrays*
Arrays.sort(a3);
System.out.println(
"The median of two sorted arrays is: " + findMedian(a3, n));
}
}

**Python code:**

```
def findMedian(a, n):
```*# When the length of the array is even*
if n % 2 == 0:
z = n // 2
e = a[z]
q = a[z - 1]
result = (e + q) / 2
return result
*# When length of array is odd*
else:
z = n // 2
result = a[z]
return result
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
*# merging both the arrays*
a3 = a1 + a2
*# Sorting the merged arrays*
a3.sort()
print("The median of two sorted array is: ",
findMedian(a3, len(a3)))

**Output:**

```
The median of two sorted arrays is: 6
```

**Complexity Analysis**

In this approach of finding the median of two sorted arrays of different lengths, we have merged both the input arrays into a merged array, we are then finding the mid element of the merged array according to the size of the array.

**Time Complexity**

So, the time complexity is **O((n+m) log (n+m))**.

**Space Complexity**

We are using a merged array as extra space. So, space complexity is **O(n + m)**.

### Approach 4: Binary Search

Another efficient approach to finding the median of two sorted arrays can be applying binary search and dividing the arrays into halves and finding the required median.

In this approach, we are not merging the array and performing a binary search but we are using the algorithm specified below.

Let us assume that we are provided two input arrays of varying lengths A, and B. (Here, the first array i.e. A is smaller in size). The size of the array A is n and the size of array B is m.

For example, array A = [ 1, 4, 7 ] and array B = [ 2, 3, 5, 6 ]

Let us see the algorithm using the above example.

We can say that the sum of the left part of both array A and array B will result in the left part of the resultant merged array.

Similarly, the sum of the right part of both array A and array B will result in the right part of the resultant merged array.

The merged array will be [ 1, 2, 3, 4, 5, 6, 7 ]

In this example, our median is 4. So, we can easily discard the right half of the combined array. Hence, in this approach, we will try to discard the part of the array that will not contain our answer.

**Algorithm**

The pseudo-code for the algorithm can be:

```
1. Find the mid part i.e. (n + m – 1) / 2.
2. If A[i-1] <= B[j] and B[j-1]<=A[i] then return the i index.
3. Else if A[i – 1] > B[j], then we need to goto the left and update i to mid - 1.
4. Repeat the above process.
```

**Implementation**

**C++ code:**

```
#include <bits/stdc++.h>
using namespace std;
```*// a function that return the median of the two arrays*
double findMedian(vector<int> &A, vector<int> &B) {
int n = A.size();
int m = B.size();
*// if the first array is larger then swap*
if (n > m)
return findMedian(B, A);
int start = 0;
int end = n;
int mergedMid = (n + m + 1) / 2;
while (start <= end) {
*// we are using MIN and MIX to maintain the overflow range*
*// checking overflow of indices*
int mid = (start + end) / 2;
int A_left_size = mid;
int B_left_size = mergedMid - mid;
int A_left = (A_left_size > 0)
? A[A_left_size - 1]
: INT_MIN;
int B_left = (B_left_size > 0) ? B[B_left_size - 1] : INT_MIN;
int A_right = (A_left_size < n) ? A[A_left_size] : INT_MAX;
int B_right = (B_left_size < m) ? B[B_left_size] : INT_MAX;
*// if the correct partioning is done then check further else change the start or end pointer*
if (A_left <= B_right and B_left <= A_right) {
if ((m + n) % 2 == 0)
return (max(A_left, B_left) + min(A_right, B_right)) / 2.0;
return max(A_left, B_left);
}
else if (A_left > B_right) {
end = mid - 1;
}
else
start = mid + 1;
}
return 0.0;
}
int main() {
vector<int> a1 = {1, 2, 3, 6};
vector<int> a2 = {4, 7, 8, 10, 22};
int n1 = sizeof(a1) /
sizeof(a1[0]);
int n2 = sizeof(a2) /
sizeof(a2[0]);
cout << "The median of two sorted arrays is: " << findMedian(a1, a2);
return 0;
}

**Java code:**

```
public class Test {
```*// a function that return the median of the two arrays*
static double findMedian(int[] A, int[] B) {
int n = A.length;
int m = B.length;
*// if the first array is larger then swap*
if (n > m)
return findMedian(B, A);
int start = 0;
int end = n;
int mergedMid = (n + m + 1) / 2;
while (start <= end) {
*// we are using MIN and MIX to maintain the overflow range*
*// checking overflow of indices*
int mid = (start + end) / 2;
int A_left_size = mid;
int B_left_size = mergedMid - mid;
int A_left = (A_left_size > 0)
? A[A_left_size - 1]
: Integer.MIN_VALUE;
int B_left = (B_left_size > 0) ? B[B_left_size - 1] : Integer.MIN_VALUE;
int A_right = (A_left_size < n) ? A[A_left_size] : Integer.MAX_VALUE;
int B_right = (B_left_size < m) ? B[B_left_size] : Integer.MAX_VALUE;
*// if the correct partioning is done then check further else change the start or end pointer*
if (A_left <= B_right && B_left <= A_right) {
if ((m + n) % 2 == 0)
return (Math.max(A_left, B_left)
+ Math.min(A_right, B_right))
/ 2.0;
return Math.max(A_left, B_left);
} else if (A_left > B_right) {
end = mid - 1;
} else
start = mid + 1;
}
return 0.0;
}
public static void main(String args[]) {
int a1[] = { 1, 2, 3, 6 };
int a2[] = { 4, 7, 8, 10, 22 };
System.out.println(
"The median of two sorted arrays is: " + findMedian(a1, a2));
}
}

**Python code:**

*# a function that return the median of the two arrays*
def findMedian(A, B):
n = len(A)
m = len(B)
*# if the first array is larger then swap *
*# checking overflow of indices*
if (n > m):
return findMedian(B, A)
start = 0
end = n
mergedMid = (n + m + 1) // 2
while (start <= end):
"""
we are using MIN and MIX to maintain the overflow range.
"""
mid = (start + end) // 2
A_left_size = mid
B_left_size = mergedMid - mid
A_left = A[A_left_size - 1] if (A_left_size > 0) else float('-inf')
B_left = B[B_left_size - 1] if (B_left_size > 0) else float('-inf')
A_right = A[A_left_size] if (A_left_size < n) else float('inf')
B_right = B[B_left_size] if (B_left_size < m) else float('inf')
*# if the correct partioning is done then check further else change the start or end pointer*
if A_left <= B_right and B_left <= A_right:
if ((m + n) % 2 == 0):
return (max(A_left, B_left) + min(A_right, B_right)) / 2.0
return max(A_left, B_left)
elif (A_left > B_right):
end = mid - 1
else:
start = mid + 1
if __name__ == '__main__':
a1 = [1, 2, 3, 6]
a2 = [4, 7, 8, 10, 22]
print("The median of two sorted array is: ",
findMedian(a1, a2))

**Output:**

```
The median of two sorted array is: 6
```

**Complexity Analysis**

In this approach to finding the median of two sorted arrays of different lengths, we have performed a binary search on the array.

**Time Complexity**

So, the time complexity is **O(min(log m, log n))**.

**Space Complexity**

We are not using any extra space. So, space complexity is **O(1)**.

## Conclusion

- The most basic approach to finding the median of two sorted arrays of the same length can be counting the first n sorted elements of the merged array. In this approach, the time complexity is
**O(n)**and space complexity is**O(1)**. - Another approach to finding the medians of two sorted arrays of the same length, can be finding the medians of both the arrays and then comparing them. In this approach, the time complexity is
**O(log n)**and space complexity is**O(1)**. - Another approach to finding the medians of two sorted arrays of the same length first can be finding the union of both the arrays and then sorting them respectively. In this approach, the time complexity is
**O(n log n)**and space complexity is**O(1)**. - The basic approach to finding the median of two sorted arrays of different lengths can be counting the first n sorted elements of the merged array. In this approach, the time complexity is
**O(m + n)**and space complexity is**O(1)**. - Another approach to finding the median of two sorted arrays of different lengths can be finding the median of both the arrays and then discarding the one half (sub-array) of both the arrays. In this approach, the time complexity is
**O(min(log m, log n)**and space complexity is**O(1)**. - Another approach to finding the median of two sorted arrays of different lengths can be merging the two arrays into a single array and then sorting it. Now, we can easily find the median and return it. In this approach, the time complexity is
**O((n+m) log (n+m))**and space complexity is**O(n + m)**. - Another approach to finding the median of two sorted arrays of different lengths can be applying binary search and diving the arrays into halves and finding the required median. In this approach, the time complexity is
**O(min(log m, log n))**and space complexity is**O(1)**.