## Median of Two Sorted Array of the Same Size #### Understanding The Problem

Problem Description

There are two sorted arrays nums1 and nums2 of size n. Find the median of the two sorted arrays.

You may assume nums1 and nums2 cannot be both empty.

Example 1:

``````nums1 = [1, 3]
nums2 = [2, 4]``````
``The median is 2.5 as (2 + 3) / 2 = 2.5``

Example 2:

``````nums1 = [1, 2, 9]
nums2 = [3, 4, 7]``````
``The median is (3 + 4)/2 = 3.5``
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 odd n, Median ( M ) = ``` value of (( n + 1)/2)th item term ``` .

For even n, Median ( M ) = ``` value of {( n /2)th item term + ( n /2 + 1)th item term}/2 ```

Note → Since the size of the two input arrays for which we are looking for the median is even(2n), we need to take the average of the middle two numbers and return it.

#### Solutions

We will be discussing linear and logarithmic solutions for the problem

1. Counting while comparing — Find the middle elements after merging the sorted array using the merge procedure of merge sort.
2. Comparing medians — Get the medians of two sorted arrays and compare the medians and move accordingly until the two medians become equal following divide and conquer approach.

#### 1. Counting While Comparing

For this approach, we actually have to find those two elements that could be in the middle when the two arrays are merged in sorted order.

If we follow the merge procedure like the one in merge sort then we could just compare the values at the two pointers pointing two the indexes of the two arrays and then increment the pointers accordingly while keeping track of the count. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array.

Solution Steps
1. Create two pointers ``` i ``` and ``` j ``` pointing two ``` nums1 ``` and ``` nums2 ``` respectively and initialize them with ``` 0 ```
2. If the value at ``` nums1[i] < nums2[j] ``` then increment ``` i ``` otherwise, increment ``` j ```
3. Repeat step 2 until ``` i ``` or ``` j ``` becomes ``` i+j ``` equals to n
4. Return median of the two elements at ith and jth indexes.
Pseudo Code
``````float getMedian(int num1[], int num2[], int size) {
int i = 0
int j = 0
int m1 = -1, m2 = -1
for (count = 0 to size) {
if (i == size) {
m1 = m2
m2 = num2
break
}
else if (j == size) {
m1 = m2
m2 = num1
break
}
if (num1[i] < num2[j]) {
m1 = m2
m2 = num1[i]
i = i + 1
} else {
m1 = m2
m2 = num2[j]
j = j + 1
}
}
return (m1 + m2)/2
}``````
Complexity Analysis

Time Complexity: O(n), where is the size of both the input arrays

Space Complexity: O(1)

Critical Ideas to Think
• Did you recognize that the merge approach is similar to the one used in merge sort?
• Why we are returning (m1 + m2)/ 2 in the end?
• If we have created an auxiliary array and save both the arrays in a sorted manner and then return its median, will it give the correct result? If yes then what would be its time and space complexity?

#### 2. Comparing medians

This approach works by comparing the two medians of both the array following the Divide & Conquer paradigm. If the first median is greater than the second median then we will look for the median of the two sorted arrays in ``` num1[0 to median1] ``` and ``` num2[median2 to n] ``` . ( Why?)

We know that ``` median1 ``` is larger than or equal to the first half of ``` num1 ``` . And the same for ``` median2 ``` and ``` num2 ``` . At the same time, we also know that ``` median1 ``` is smaller than or equal to the second half of ``` num1 ``` .

Let’s consider the case ``` median1 > median2 ```

``````num1:      [.....median1.....]
num2:      [.....median2.....]
num1+num2: [.....median2...median1........]``````

Let us call the median of the merged array ``` m* ``` . Since the first halves of ``` num1 ``` and ``` num2 ``` come before ``` median1 ``` . So, ``` median1 >= m* ``` , this means that no values larger than ``` median1 ``` need to be considered in ``` num1 ``` . So we only need to look in the first half or ar1.

Similarly, since the second halves of ``` num1 ``` and ``` num2 ``` come after ``` median1 ``` , we have that ``` median2 <= m* ``` , this means that no values smaller than ``` median2 ``` need to be considered and we only need to look in the second half of ``` num2 ``` .

Example →

``````num1 = {1, 12, 15, 26, 38}
num2 = {2, 13, 17, 30, 45}``````
``med1 = 15 and med2 = 17 for num1[0 to 4] and num2[0 to 4]``
``````med1 < med2. So median is present in {15, 26, 38} and {2, 13, 17}
now, med1 = 26 and med2 = 13``````
``med1 > med2. So median is present in {15, 26} and {13, 17}``
``````The size of both the subarrays are now 2. So,
median = (max(15,13) + min(26, 17))/2 = 16``````
Solution Steps
1. Calculate the median of both the arrays, say ``` m1 ``` and ``` m2 ``` for ``` num1[] ``` and ``` num2[] ``` .
2. Repeat till the size of ``` num1 ``` and ``` num2 ``` becomes two.
• If ``` m1 == m2 ``` then return m1.
• If ``` m1 > m2 ``` then median will be present in either of the sub-arrays ``` num1[0..m1] ``` and ``` num2[m2 to n] ``` .
• If ``` m2 > m1 ``` then median will be present in either of the sub-arrays ``` num1[m1 to n] ``` and ``` num2[0 to m2] ``` .

3. Return ``` Median = (max(array1,array2) + min(array1,array2))/2 ```

Pseudo Code
``````float getMedian(int num1[], int num2[], int size) {
// base cases
if (size <= 0)
return -1
if (size == 1)
return (num1 + num2) / 2
if (size == 2)
return (max(num1, num2) + min(num1, num2)) / 2
int med1 = median(num1, size)
int med2 = median(num2, size)
// compare the medians
if (med1 == med2)
return med1
if (med1 < med2) {
// recurse for the subarray num1[m1 to size] and num2[0 to m2]
if (size % 2 == 0)
return getMedian(num1 + size/2 - 1, num2, size - size/2 + 1)
else
return getMedian(num1 + size / 2, num2, size - size / 2)
} else {
// recurse for the subarray num1[0 to m1] and num2[m2 to n]
if (size % 2 == 0)
return getMedian(num2 + size / 2 - 1, num1, size - size / 2 + 1)
else
return getMedian(num2 + size / 2, num1, size - size / 2)
}``````
``````// Utility function to find median of array
int median(int arr[], int array_size) {
if (array_size % 2 == 0)
return (arr[array_size / 2] + arr[array_size / 2 - 1]) / 2
else
return arr[array_size / 2]
}``````
Complexity Analysis

Time Complexity: O(log n), where n is the size of both the arrays

Space Complexity: O(log n) (Why?)

Critical Ideas to Think
• Can you code this approach in an iterative manner?
• Why does the comparison of medians and moving accordingly will reach the correct result?
• What would be the median when the two sorted arrays are of length two?

#### Comparison of Different Solutions #### Suggested Problems to Solve

• Median of two sorted arrays of different sizes
• Median in a row-wise sorted matrix