Question

Suppose you have two sorted arrays of n integers: X0[1..n] and X1[1..n]. Devise and analyze an efficient algorithm for finding the median of all numbers in arrays X0 and X1. Now, suppose you have not two, but three such arrays, each with n elements. Devise and analyze an efficient algorithm for finding the median. Do the same for n arrays, each with n elements.

Answer 1

Median: To get median we need to sort array and find the middle element .that will be median

Steps to get the median

Consider array {6,3,7,8,1}

For the given array we need o sort the array first

Then the sorted array is{1,3,6,7,8}

Then median is middle element. So for the given example median is 6.

Consider the array are given below

X=[4,2,7]

Y=[1,8]

For finding median first we need to combine the two arrays.

Then the result is

Z=[1,2,4,7,8]

So the median is middle element. So 8 is the median

What I explained above is no of elements if its odd.
Suppose the total no of element is even what will be the median. Lets find out.

Consider the same arrays with addition of one more element 5 in Y.

So our array will look like

X=[4,2,7]

Y=[1,8,5]

For finding median first we need to combine the two arrays.

Then the result is

Z=[1,2,4,5,7,8]

Here we cannot choose the middle element. The total no of element is 6.so will pick

3^rd and 4^th element which 4 and 5 respectively and take the average of that.

Then that will be median.

Ie (4+5)/2=4.5

Now I am trying to introduce new algorithm which is efficient to sort 2 arrays.

Using median of one array set against other array median

Consider r1 and r2 are two arrays

-find out the median of r1 and r2.lets say the median of r1 as s1 and median of r2 as s2.

-suppose s1=s2 .then we found out median in first step itself.

-suppose s1!=s2 and s1>s2 then median will be in

From first no of r1 to s1 or will be in first no of r2 to s2

- suppose s1!=s2 and s2>s1 then median will be in

From last no of r1 to s1 or will be in last no of r2 to s2

-this procedure should repeat until the count become 2.

-when the count is 2 use the equation to find out median

We call median of 2 arrays as D

Then D=(LARGEST OF(S1[0],S2[0]+SMALLEST OF(S1[1],S2[1]))/2