Yup, my bad. Its not O(logn) but O(n) algorithm to find median. Shishir, are you sure that your algorithm will emit K elements CLOSEST to median?
_dufus On Aug 31, 12:56 pm, Shishir Mittal <[email protected]> wrote: > First find the median of the array in O(n) time using *'Linear general > selection algorithm - "Median of Medians algorithm" '* > (http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selec...) > by finding (n+1)/2 smallest element (for odd n). You can also refer Pg 189, > Introduction of Algorithms , II edition (Cormen) for the algorithm. > > Then apply the same algorithm to partition the array by locating the (k+1)th > smallest element. In the corresponding partition function instead of > directly comparing the values at two indexes use a compare function which > compares modulus of difference of the element and the median found ie > > int compare (int a, int b, int median){ > return ( abs(median - a) - abs(median - b)) ; > > } > > Overall time complexity : O(n), space complexity : O(1). > > On Sun, Aug 30, 2009 at 8:36 PM, Dufus <[email protected]> wrote: > > > Is it acceptable if I > > find the median in O(logn) time and then, > > Can you elaborate how can we find the median of an unsorted array in O(log > n) time? > > > find k numbers closest to the median in O(k) space and O(n) time? > > > _dufus > > > On Aug 30, 4:38 pm, Nagendra Kumar <[email protected]> wrote: > > > Given a set S of n distinct numbers and a positive integer k <= n. > > > Determine the k numbers in S that are closest to the median of S. > > > Find an O(n) algorithm > > -- > Shishir Mittal > Ph: +91 9936 180 121 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
