{{task heading}}

Write a program to find the &nbsp; [[wp:Median|median]] &nbsp; 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. &nbsp; In that case, return the average of the two middle values.

There are several approaches to this. &nbsp; 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>
