Problem: There are two sorted arrays of size n each. Write an algorithm to find the median of the array obtained after merging the given two arrays.
Algorithm:
1) Calculate the medians med1 and med2 of the input arrays arr1[]
and arr2[].
2) If med1 and med2 both are equal then return med1.
3) If med1 is greater than med2, then median is present in one
of the below two subarrays.
a) From first element of arr1 to med1.
b) From med2 to last element of arr2.
4) If med2 is greater than med1, then median is present in one
of the below two subarrays.
a) From med1 to last element of arr1.
b) From first element of arr2 to med2.
5) Repeat the above process until size of both the subarrays becomes 2.
6) If size of the two arrays is 2 then use following formula to get the median:
Median = (MAX(arr1[0], arr2[0]) + MIN(arr1[1], arr2[1]))/2
Implementation:
inline int MAX(int i, int j)
{
return i > j ? i : j;
}
inline int MIN(int i, int j)
{
return i < j ? i : j;
}
int median(int *arr, int n)
{
if(n % 2 == 0)
return (arr[n/2] + arr[n/2 - 1]) / 2;
else
return arr[n/2];
}
int getMedian(int *arr1, int *arr2, int n)
{
if(n <= 0)
return -1;
if(n == 1)
return (arr1[0] + arr2[0]) / 2;
if(n == 2)
return (MAX(arr1[0], arr2[0]) + MIN(arr1[1], arr2[1])) / 2;
int med1 = median(arr1, n);
int med2 = median(arr2, n);
if(med1 == med2)
return med1;
if(med1 < med2)
{
if(n % 2 == 0)
return getMedian(arr1 + n/2 - 1, arr2, n - n/2 + 1);
else
return getMedian(arr1 + n/2, arr2, n - n/2);
}
else
{
if(n % 2 == 0)
return getMedian(arr1, arr2 + n/2 - 1, n - n/2 + 1);
else
return getMedian(arr1, arr2 + n/2, n - n/2);
}
}
Time Complexity: O(logn)
Algorithm:
1) Calculate the medians med1 and med2 of the input arrays arr1[]
and arr2[].
2) If med1 and med2 both are equal then return med1.
3) If med1 is greater than med2, then median is present in one
of the below two subarrays.
a) From first element of arr1 to med1.
b) From med2 to last element of arr2.
4) If med2 is greater than med1, then median is present in one
of the below two subarrays.
a) From med1 to last element of arr1.
b) From first element of arr2 to med2.
5) Repeat the above process until size of both the subarrays becomes 2.
6) If size of the two arrays is 2 then use following formula to get the median:
Median = (MAX(arr1[0], arr2[0]) + MIN(arr1[1], arr2[1]))/2
Implementation:
inline int MAX(int i, int j)
{
return i > j ? i : j;
}
inline int MIN(int i, int j)
{
return i < j ? i : j;
}
int median(int *arr, int n)
{
if(n % 2 == 0)
return (arr[n/2] + arr[n/2 - 1]) / 2;
else
return arr[n/2];
}
int getMedian(int *arr1, int *arr2, int n)
{
if(n <= 0)
return -1;
if(n == 1)
return (arr1[0] + arr2[0]) / 2;
if(n == 2)
return (MAX(arr1[0], arr2[0]) + MIN(arr1[1], arr2[1])) / 2;
int med1 = median(arr1, n);
int med2 = median(arr2, n);
if(med1 == med2)
return med1;
if(med1 < med2)
{
if(n % 2 == 0)
return getMedian(arr1 + n/2 - 1, arr2, n - n/2 + 1);
else
return getMedian(arr1 + n/2, arr2, n - n/2);
}
else
{
if(n % 2 == 0)
return getMedian(arr1, arr2 + n/2 - 1, n - n/2 + 1);
else
return getMedian(arr1, arr2 + n/2, n - n/2);
}
}
Time Complexity: O(logn)
No comments:
Post a Comment