0

I would like to know if there exists an algorithm to find the median of an array of odd length. Obviously one could just sort the array and take the middle but ideally by only being interested in the median one could make gains in terms of time complexity of the algorithm.

If no such algorithm exists, any suggestions regarding how to go about developing such an algorithm would be great.

Thanks

fred
  • 117
  • 1
  • 1
  • 5
  • I don't see any way of doing some type of sorting, which means you're probably looking at `O(NlgN)` for a solution. Is there some reason why you don't want to sort? – Tim Biegeleisen Sep 13 '16 at 01:07
  • Look at K-selection algorithms. Example: https://en.wikipedia.org/wiki/Quickselect – MBo Sep 13 '16 at 01:09

3 Answers3

0

This is solved by a selection algorithm, and can be done in O(n) time. Quickselect, or its refinement introselect, are popular methods.

A very brief summary of quickselect is to run quicksort, but rather than sorting both halves at each step, you only sort the half that contains the element you're looking for, which can be determined by counting how many elements are in each partition.

C++, for example, actually has this as a standard library function: nth_element.

0

You can use the Selection algorithm that can find the kth smallest element of an array with k is the half of the size of the array.

For unstructured data, it's within O(n).

But always keep in mind, that theoretical complexity is not everything!

Read also this question.

Community
  • 1
  • 1
sascha
  • 32,238
  • 6
  • 68
  • 110
0

Yes, an algorithm exists. The problem you are talking about is finding the kth largest element where k is the value of half+1 of the array length. Here is a link to a way to do it in O(n) time, Median of medians.

D. Law.
  • 234
  • 1
  • 3
  • 8