How do you find the median of a list in Python? The list can be of any size and the numbers are not guaranteed to be in any particular order.
If the list contains an even number of elements, the function should return the average of the middle two.
Here are some examples (sorted for display purposes):
median([1]) == 1
median([1, 1]) == 1
median([1, 1, 2, 4]) == 1.5
median([0, 2, 5, 6, 8, 9, 9]) == 6
median([0, 0, 0, 0, 4, 4, 6, 8]) == 2
I had some problems with lists of float values. I ended up using a code snippet from the python3 statistics.median and is working perfect with float values without imports. source
Of course you can use build in functions, but if you would like to create your own you can do something like this. The trick here is to use ~ operator that flip positive number to negative. For instance ~2 -> -3 and using negative in for list in Python will count items from the end. So if you have mid == 2 then it will take third element from beginning and third item from the end.
You can try the quickselect algorithm if faster average-case running times are needed. Quickselect has average (and best) case performance
O(n)
, although it can end upO(n²)
on a bad day.Here's an implementation with a randomly chosen pivot:
You can trivially turn this into a method to find medians:
This is very unoptimised, but it's not likely that even an optimised version will outperform Tim Sort (CPython's built-in
sort
) because that's really fast. I've tried before and I lost.Here's the tedious way to find median without using the
median
function:Here what I came up with during this exercise in Codecademy: