Let clusterRange(k,r) be a value representing the range or maximum difference in

Question

Let clusterRange(k,r) be a value representing the range or maximum difference in value of
k numbers in a set S that are the kth closest numbers to the rth ranked element of S (which containts
a total of n distinct numbers.) Describe an ecient algorithm that
(a) Finds the k numbers that are closest to the rth ranked element.
(b) Computes clusterRange(k,r)
(c) Returns the rank ^r of the element with the smallest value of clusterRange(k,r), r in S, where S is
a set of ranks.
Analyze the running time complexity.

Explanation / Answer

Code to Finds the k numbers that are closest to the rth ranked element is

// Program in Java to find k closest elements to a given value
class KNearest
{

int Find(int Array[], int lowest, int highest, int x)
{
// Base cases
if (Array[highest] <= x) // x is greater than all
return highest;
if (Array[lowest] > x)
return lowest;

// Find the middledle point
int middle = (lowest + highest)/2;

if (Array[middle] <= x && Array[middle+1] > x)
return middle;

if(Array[middle] < x)
return Find(Array, middle+1, highest, x);

return Find(Array, lowest, middle - 1, x);
}

// This function prints k nearest or closest elements to x in Array[].

void printKNearest(int Array[], int x, int k, int n)
{
int l = Find(Array, 0, n-1, x);
int r = l+1; //Right index
int count = 0; // the keep count

if (Array[l] == x) l--;

while (l >= 0 && r < n && count < k)
{
if (x - Array[l] < Array[r] - x)
System.out.print(Array[l--]+" ");
else
System.out.print(Array[r++]+" ");
count++;
}

while (count < k && l >= 0)
{
System.out.print(Array[l--]+" ");
count++;
}

while (count < k && r < n)
{
System.out.print(Array[r++]+" ");
count++;
}
}

/* Driver program */
public static void main(String args[])
{
KNearest ob = new KNearest();
int Array[] = {11, 26, 12, 20, 35, 39, 42,
45, 48, 50, 54, 55, 56
};
int n = Array.length;
int x = 35, k = 4;
ob.printKNearest(Array, x, 4, n);
}
}

time complexity is O(n) and time taken to find optimized solution to find kth element is  O(Logn + k).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.