Use a divide-and-conquer algorithm to find the median, rearranging the array so that the values less than the median precede it in the array and the values greater than the median follow it. So the median is a(n/ 2). Now use the divide-and-conquer algorithm twice more to locate the (n/2-k)th and (n/2+k)th elements. Finally, march out both directions from n/2, selecting the closest elements to a(n/2). Each of these operations can be done in O(n), so the total algorithm is O(n).
Dave On Apr 21, 9:35 am, Algo <[EMAIL PROTECTED]> wrote: > hi this is prob 9-3.7 of CLRS , anybody having a clue??? > > Describe an O(n)-time algorithm that, given a set S of n distinct > numbers and a positive > integer k ≤ n, determines the k numbers in S that are closest to the > median of S > > thanks in advance.. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
