Median
There are quite a few
How to find median of unsorted array in O(n) time? (i.e. without sorting)
- Came up in this problem https://codeforces.com/contest/1993/problem/D
I think we saw it in CS240, through Quickselect, we can do O(n), but worst case is O(n^2)?
Other codeforce problem
If you want to find a point that minimizes the distance to all other points, you can just use the median. Why?
- Picture that the points are sorted. As you move your point by 1 to the right, there are n-1 distances that are reduced by 1, and 1 that is increased by 1. So always positive. This is no longer true after you get pass the median.
Okay, why is squared distance minimum the mean then?
- Squared distance “punishes” being far away much more.
- The point that perfectly balances out all these penalties is exactly the “center of mass” — the mean.
- If you go to the right of the mean, the sum of squared distances gets bigger, because those far-away points grow quadratically in penalty.