1 votes 1 votes how to find median of an array in O(N) time Kaluti asked Nov 5, 2017 Kaluti 479 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply joshi_nitish commented Nov 5, 2017 reply Follow Share i think it can't be found in O(n) time....tightest upperbound to do so is O(nlogn), but, you can use randomized partitioning algorihtm-> in this you can randomly select one element and apply partition algorithm(as in quicksort),it will take O(n)... then check if both side of partition contain equal element in O(n) if you are lucky enough, you can find median in O(n) // though it depends on luck in random selection... but absolute algorithm to find median will take O(nlogn) time.. 0 votes 0 votes srestha commented Nov 5, 2017 reply Follow Share @ joshi_nitish what median means? median means middle element of sorted array So, why not we put binary search here and find midean in O(1) time? 0 votes 0 votes joshi_nitish commented Nov 5, 2017 reply Follow Share @srestha, firstly bianry search is not possible because array is not sorted.. secondaly, So, why not we put binary search here and find midean in O(1) time? what you mean by this???....if the array would be sorted, then also no need to apply binary search...median in that case will be middle element and can be found in O(1) time... 1 votes 1 votes srestha commented Nov 5, 2017 reply Follow Share "median means middle element of sorted array" 0 votes 0 votes joshi_nitish commented Nov 5, 2017 reply Follow Share @srestha, yes median means middle element of sorted array... 0 votes 0 votes srestha commented Nov 5, 2017 reply Follow Share so find mid in O(1) time possible, right? 0 votes 0 votes Hemant Parihar commented Nov 5, 2017 reply Follow Share @ joshi_nitesh see this, it can be done in O(n) time. It is not only about median element they are finding the any (k)th smallest element in O(n) times. So using this, you can find n/4 th smallest element also, Whereas median will be (n/2)th smallest element. https://cs.stackexchange.com/questions/1914/to-find-the-median-of-an-unsorted-array http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/ 4 votes 4 votes joshi_nitish commented Nov 5, 2017 reply Follow Share it is possible when the given array is sorted....but in qsn it is not menioned that array is sorted.. 0 votes 0 votes joshi_nitish commented Nov 5, 2017 reply Follow Share @Hemant Parihar thankyou for sharing... 0 votes 0 votes Kaluti commented Nov 6, 2017 reply Follow Share by using median of median algorithm we can find median of an sorted array in O(n) time 0 votes 0 votes chandra sai commented Nov 6, 2017 reply Follow Share isn't it true that median for sorted array is always middle element? if yes ,then why to use O(n) algorithms instead of just reaching middle element in O(1) time?? 0 votes 0 votes Please log in or register to add a comment.