Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding the median of an unsorted array

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median. But this approach would take O(nlogn) time.

Can we do the same by some method in O(n) time? If we can, then please tell or suggest some method.

like image 722
Luv Avatar asked May 19 '12 03:05

Luv


People also ask

How do you find the median without sorting?

You can certainly find the median of an array without sorting it. What is not easy is doing that efficiently. For example, you could just iterate over the elements of the array; for each element, count the number of elements less than and equal to it, until you find a value with the correct count.

How do you find the median of an unsorted list in Python?

To find the median of an unsorted array, we can make a min-heap in O(nlogn) time for n elements, and then we can extract one by one n/2 elements to get the median.


2 Answers

You can use the Median of Medians algorithm to find median of an unsorted array in linear time.

like image 152
Sergey Kalinichenko Avatar answered Sep 21 '22 11:09

Sergey Kalinichenko


I have already upvoted the @dasblinkenlight answer since the Median of Medians algorithm in fact solves this problem in O(n) time. I only want to add that this problem could be solved in O(n) time by using heaps also. Building a heap could be done in O(n) time by using the bottom-up. Take a look to the following article for a detailed explanation Heap sort

Supposing that your array has N elements, you have to build two heaps: A MaxHeap that contains the first N/2 elements (or (N/2)+1 if N is odd) and a MinHeap that contains the remaining elements. If N is odd then your median is the maximum element of MaxHeap (O(1) by getting the max). If N is even, then your median is (MaxHeap.max()+MinHeap.min())/2 this takes O(1) also. Thus, the real cost of the whole operation is the heaps building operation which is O(n).

BTW this MaxHeap/MinHeap algorithm works also when you don't know the number of the array elements beforehand (if you have to resolve the same problem for a stream of integers for e.g). You can see more details about how to resolve this problem in the following article Median Of integer streams

like image 38
rkachach Avatar answered Sep 20 '22 11:09

rkachach