Problem from "Competitive Programmer’s Handbook" by Antti Laaksonen, Page 61.

The problem is to find x to minimum the sum of the equation below:

I thought the answer will be the mean on the number because if we plot the in a 1D number line, the mean will be somewhere middle of them, so the absolute difference of distance between each number and the mean can be minimized.

The book says it is the median.

Example [1, 2, 2, 6, 9]

The mean will be 19 / 5 = 3.8. The absolute difference is 13.8.

The median is 2 an the absolute difference is 12.

I know that this is the absolute sum not the just the sum. But the median is only limited to the element of the array. Why x should be the median instead of the mean? Can this be mathematically proved?