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;
}```