{{task heading}}

Write a program to find the   [[wp:Median|median]]   value of a vector of floating-point numbers.

The program need not handle the case where the vector is empty, but ''must'' handle the case where there are an even number of elements.   In that case, return the average of the two middle values.

There are several approaches to this.   One is to sort the elements, and then pick the element(s) in the middle.

Sorting would take at least &nbsp; <big><span style="font-family: serif">O(''n'' log''n'')</span></big>. &nbsp; Another approach would be to build a priority queue from the elements, and then extract half of the elements to get to the middle element(s). &nbsp; This would also take &nbsp; <big><span style="font-family: serif">O(''n'' log''n'')</span></big>. &nbsp; The best solution is to use the &nbsp; [[wp:Selection algorithm|selection algorithm]] &nbsp; to find the median in &nbsp; <big><span style="font-family: serif">O(''n'')</span></big> &nbsp; time.

{{task heading|See also}}
[[Quickselect_algorithm]]
{{Related tasks/Statistical measures}}

<hr>