#### Arrays & Strings

**Problem **

Find the **median** of two **sorted** arrays.

Consider an array **{ 1, 3, 17, 26, 38 }** **[ Odd no. of elements ]**

Median = **arr[n/2] = arr[5/2] = arr[2] = 17**

For an array with even no. of elements,

Median = **( ( arr[n/2] + arr[n/2 + 1] ) / 2 )**

For e.g, Median for the array **{ 1, 3, 17, 23, 26, 38 }** is **(17 + 23) / 2 = 20**

Given two sorted arrays, find the median of the resultant array formed after merging.

**Solution **

We can simple merge the two sorted arrays and then find median of the resultant algorithm.

But we will go for a better and more efficient approach.

Let’s explain the approach with an example :-

Consider the arrays arr1 = **{ 1, 3, 17, 26, 38 }** and arr2 = **{ 2, 7, 8, 30, 46 }**

1st Iteration :: Median of arr1 = **17** & Median of arr2 = **8**

Since **median**(arr1) > **median**(arr2), so we can conclude that median would be in 1st half of **arr1** &

2nd half of **arr2**.

Thus we need to consider **{ 1, 3, 17 }** of arr1 and **{ 8, 30, 46 }** of arr2.

2nd Iteration :: Median would be in **{ 3, 17 }** of arr1 & **{ 8, 30 }** of arr2.

3rd Iteration :: We get the final median = **(17 + 8) / 2 = 12** [boundary condition]

**Boundary conditions :-**

**Median for 2 sorted arrays of size 2 :-**

Consider arr1 = **{ 3, 17 }** and arr2 = **{ 8, 30 }** .

Median = ( **max**(arr1[0], arr2[0]) + **min**(arr1[1], arr2[1]) ) / 2 = ( **max**(3,8) + **min**(17,30) ) / 2 = ( 8 + 17 ) / 2 = 12.

**Median for 2 sorted arrays of size 1 :-**

Consider arr1 = **{ 5 }** & **{ 3 }**.

Median = ( arr1[0] + arr2[0] ) / 2 = ( 5 + 3 ) / 2 = 4.

#include<iostream> using namespace std; int max(int a, int b) { return ((a > b) ? a : b); } int min(int a, int b) { return ((a < b) ? a : b); } // get median of an array int median(int arr[], int size) { if (size % 2 == 0) return (arr[size/2] + arr[size/2-1])/2; else return arr[size/2]; } // get the median of two sorted arrays int medianSortedArrays(int arr1[], int arr2[], int size) { int med1; int med2; if(size <= 0) return -1; if(size == 1) return (arr1[0] + arr2[0])/2; if (size == 2) return (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1])) / 2; med1 = median(arr1, size); // median of the first array med2 = median(arr2, size); // median of the second array // we can return either med1 or med2 if(med1 == med2) return med1; if (med1 < med2) { // median lies in 2nd half of 1st array and 1st half of 2nd array return medianSortedArrays(arr1 + size/2, arr2, size - size/2); } else { // median lies in 1st half of 1st array and 2nd half of 2nd array return medianSortedArrays(arr2 + size/2, arr1, size - size/2); } } // main int main() { int arr1[] = {1, 3, 17, 26, 38}; int arr2[] = {2, 7, 8, 30, 46}; //1,2,3,7,8,17,26,38,46 //1,3,17 8,30,46 //3,17 8,30 //(17+8)/2 cout<<"\nMedian of the 2 sorted arrays is "<<medianSortedArrays(arr1, arr2, 5); cout<<endl; return 0; }