thanks Dave.. Deepanshu
On 4/21/08, Dave <[EMAIL PROTECTED]> wrote: > > > 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.. > > > -- Deepanshu Shukla 3rd year , Mathematics and Computing, I.T.-B.H.U. , Varanasi,India --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---