CareerCup

Use the select algorithm. It'll work in O(n)

This is a straight-forward application of order statistics algorithm from "Introduction to algorithm" By Cormen and Rivest

if two arrays are sorted then take a pointer pointing towards median of one array and start from the first element of the second array and if median is smaller then other pointer move to the next location else move other pointer.keep on doing that unless sum of position of both arrays is equal to n.

Please comment??

why to use selection or order statistics algorithms if the arrays are sorted?

Just merge them till n th element ... it runs in O(n).
(you don't have to actually merge it, just compare both arrays and keep track of the i th element till i == n).

Hey its median and not mean...
We can solve this problem in O(log n) time.
We first find the medians of each of the arrays. This takes O(1) time as they are sorted. Then we compare them. Say A,B are the arrays and Ma, Mb are their respective medians. If Ma>Mb then we can now reduce the problem to finding median of the A and B[n/2...n] combined as the combined median cannot lie in the first half of B because it would have less than n/2 elements on its left then. Thus we are halfing the array sizes each time. This can be in any order but we know that it would take 2*(log n) steps untill we find the median. Therefore total running time O(log n)

it's our algorithm course homework this week... if two arrays are already sorted, I think O(logN) will do it.

We already know the size of an Array and the each array is sorted.
We can merge the array simply comparing and put a element to new array to merge.
When we put N and N+1 elements, just calculate element of N + (element of N+1) / 2
That is median. Even we do not need to compare them more than N

Median is the middle value out of a set of values. Say we are given the values 1,3,4,6,8,9,12 then the middle value is 6. Your immediate reaction would be what if we just had 1,3,4,6,8,9 (without 12) what would the median be. In case we have an even number of terms then the average of the middle two values is taken to be the median. So in our case we take the average of 4 and 6 which is 5 as the median.

For this question note that both arrays are sorted and are of size N. So the total elements we would have would be 2N. Note that the number 2N is necessarily an even number since we multiply N by 2. This means we are specifically looking for the average of the two middle values. The middle two values among the 2N values would be the Nth and the (N+1)th terms.

For our problem the idea is simple we run the same algorithm to merge the two sorted arrays as we do in merge sort with slight modifications. We don't declare any extra space, rather we keep a count of the terms we would have added to the merged array and when we see the Nth and the (N+1)th term then we note them down take their average and return our result.


To merge the two arrays, we initialize two indexes pointing to the zeroth index of the two arrays. We compare the two elements of the two arrays pointed to by the indexes, grab the smaller element out of the two and increment that array's index whose element we chose. We also keep a count of the number of terms we have grabbed so far and increment our counter each time we grab another term. We are done when we have seen (n+1) terms since we will have the two terms needed for calculating the median..

Here's the code:

float findMedian(int[] array1, int[] array2){

int a = 0;
int b = 0;
int count = 0;
int Nth = 0;
int Nplus1th = 0;

for(int i=0; i <=N; i++){

if( array1[a] < array2[b]){
a++
count++;

if(count == N)
Nth = array1[a-1];

if(count == N+1)
Nplus1th = array1[a-1];

}


if( array1[a] > array2[b]){
b++
count++;
if(count == N)
Nth = array2[b-1];

if(count == N+1)
Nplus1th = array2[b-1];

}
}

return (Nth + Nplus1th)/2;
}

Note that the loop runs for exactly n+1 times and then exists. When the loop exists we already know the n and the n+1 terms and return their average. dges + number of nodes) in the graph.

Since we only scan N+1 elements our algorithm takes O(N+1) = O(N) time.

find median of first array .find the index of element in array 2 that is larger than median of array 1 and take a array3 as large as index.
loop through array 2 as long as the elements are less than median and do the following.
find the possible position of array2[i] in the merged version. then array3[i] = that position. Do it as long as array3[i] >= N. if it is equal to N , then array2[i] = median , and if >N then median is array[k]-diff ;diff = array3[i] - N. k is used to move in the array1.