samedi 27 décembre 2014

Find the kth smallest element from 2 sorted arrays


I came across the solution for this problem:


I would like to know the concept behind selecting the low and high values?



int findKthSmallest(int arr1[],int size1,int arr2[],int size2,int k)
{
//check whether we have k element after combining both arrays.
assert(size1 + size2 >= k);
assert(k>0);
//find index low <= w < high such that w from arr1 and (k-w) from arr2, are the smallest k numbers of resultant.
int low = max(0 , k - size2 ); //define start point
int high = min(size1 , k);//define end point

while (low < high)
{
int w = low + (high - low) /2;
//Can we include arr1[w] in the k smallest numbers that we are finding?
if ((w < size1) && (k-w > 0) && (arr1[w] < arr2[k-w-1]))
{
low = w + 1;
}
else if ((w> 0) && (k-w < size2 ) && (arr1[w-1] > arr2[k-w]))
{
//can we discard arr1[w -l] from the set of k smallest numbers.
high = w;
}
else
{
//Both the inequalities were false, break.
low = w;
break;
}
}
if (low == 0)
{
return arr2[k -1];
}
else if (low == k)
{
return arr1[k-1];
}
else
{
return max(arr1[low -1], arr2[k - low - 1]);
}
return 0;
}




Aucun commentaire:

Enregistrer un commentaire