You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
76 lines
1.6 KiB
C++
76 lines
1.6 KiB
C++
/*
|
|
* C++ Program to Find Median of Two Sorted Arrays
|
|
*/
|
|
#include <iostream>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
|
|
|
|
int median(int [], int);
|
|
|
|
/*
|
|
* returns median of ar1[] and ar2[].
|
|
*/
|
|
int getMedian(int ar1[], int ar2[], int n)
|
|
{
|
|
int m1;
|
|
int m2;
|
|
if (n <= 0)
|
|
return -1;
|
|
if (n == 1)
|
|
return (ar1[0] + ar2[0]) / 2;
|
|
if (n == 2)
|
|
return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
|
|
m1 = median(ar1, n);
|
|
m2 = median(ar2, n);
|
|
if (m1 == m2)
|
|
return m1;
|
|
if (m1 < m2)
|
|
{
|
|
if (n % 2 == 0)
|
|
return getMedian(ar1 + n / 2 - 1, ar2, n - n / 2 + 1);
|
|
else
|
|
return getMedian(ar1 + n / 2, ar2, n - n / 2);
|
|
}
|
|
else
|
|
{
|
|
if (n % 2 == 0)
|
|
return getMedian(ar2 + n / 2 - 1, ar1, n - n / 2 + 1);
|
|
else
|
|
return getMedian(ar2 + n / 2, ar1, n - n / 2);
|
|
}
|
|
}
|
|
|
|
/*
|
|
* get median of a sorted array
|
|
*/
|
|
int median(int arr[], int n)
|
|
{
|
|
if (n % 2 == 0)
|
|
return (arr[n / 2] + arr[n / 2 - 1]) / 2;
|
|
else
|
|
return arr[n / 2];
|
|
}
|
|
|
|
/*
|
|
* Main
|
|
*/
|
|
int main()
|
|
{
|
|
int ar1[] = {1, 2, 3, 6};
|
|
int ar2[] = {4, 6, 8, 10};
|
|
int n1 = sizeof(ar1)/sizeof(ar1[0]);
|
|
int n2 = sizeof(ar2)/sizeof(ar2[0]);
|
|
if (n1 == n2)
|
|
cout<<"Median is "<<getMedian(ar1, ar2, n1);
|
|
else
|
|
cout<<"Doesn't work for arrays of unequal size"<<endl;
|
|
return 0;
|
|
}
|
|
|
|
/*
|
|
Median is 5
|
|
|
|
------------------
|
|
(program exited with code: 1)
|
|
Press return to continue
|