Given an unsorted array A [1.. n ] of n distinct integers and a positive integer

Question

Given an unsorted array A[1..n] of n distinct integers and a positive integer k n, give an algorithm that takes expected O(n) time on all inputs to determine the k numbers in A that are closest in value (not closest in position) to the median of A. Note: The O(n) bound does not depend on k; e.g., running an O(n) time algorithm k times results in an O(nk) time algorithm,not an O(n) time algorithm. Also note that since order does not matter for this problem and there may be ties, your output may still be correct even if it does not match the sample output perfectly.

1. Describe your algorithm in pseudocode. Comment your code.

2. Prove that your algorithm is correct.

3. Analyze your algorithm's running time. Does your algorithm run in O(n)? Argue why.

Explanation / Answer

Given array A of n integers (or reals), find below
median = n/2;
m = select median.
a = select element n/2-k;
b = select element n/2+k;

m, a & b can be done in O(n) time using Selection algo given in Cormen book.

Now, define the array B of 2k integers (exclude the median in array B), such that all values in B are in range [a,b].
Then, do
for(int i = 0; i < 2 * k; i++)
B[i] = B[i] - m;

Now, find c = the kth smallest absolute value in array B (using a version of selection sort that considers absolute value of negative number while doing comparison).
Then, scan array B and find all numbers whose absolute value <= c and put that in array C.
for (i = 0; i < k; i++)
C[i] += m;
output array C as result.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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