Proof that median of an array is the number that minimizes the sum of manhattan distance to all points

Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come up for a proof or explanation for the same ( i.e why its not mean).

Any help is highly appreciated.

• math.stackexchange.com/questions/113270/… Jul 30, 2016 at 8:48
• Also see this answer, stackoverflow.com/a/7155426/948794 Jul 30, 2016 at 9:31
• What does "Manhattan distance" mean in this context? What did you try? Where did you get stuck? Jul 30, 2016 at 9:31
• @DavidRicherby Manhattan distance always means L1 distance. Jul 30, 2016 at 9:35
• There can easily be more than one "number that minimizes the sum of manhattan distance to all points". ​ For example, consider the sorted array [0,4]. ​ ​ ​ ​
– user12859
Jul 30, 2016 at 11:27

marks the set of numbers $$P=\{P_1,P_2,P_3, \ldots ,P_n\}$$

need to find number $$X$$:

$$|P_1-X|+|P_2-X|+\ldots+|P_n-X|=D$$, which minimizes $$D$$.

the fact that X is the median can be shown using induction on the number of numbers n in $$P$$.

Base: $$n=1$$: trivial to see that the median is $$P_1$$ and $$|P_1-P_1|=D=0$$ is minimal ($$D>=0$$).

now suppose that this holds for all $$P$$ of size $$|P|=n$$, we need to show that this holds for $$|P|=n+1$$.

In other words:

given that $$|P_1-X|+|P_2-X|+\ldots+|P_n-X|=D$$ is minimal when $$X=P_m$$ is the median of $$P=\{P_1,P_2,P_3, \ldots ,P_n\}$$ show that $$|P_1-X|+|P_2-X|+\ldots+|P_n-X|=D$$ is minimal when $$X=P_m'$$ is the median of $$P=\{P_1,P_2,P_3, \ldots ,P_{n+1}\}$$. notice that there are two cases $$m'=m+1$$ ($$n$$ is even) or $$m'=m$$ ($$n$$ is odd).

I suggest drawing a simple example using $$n=3$$ and $$n+1=4$$ on an axis. Can you see why this must hold?

• I suggest learning LaTeX and using it to enhance the way your answers look. Jan 27, 2017 at 11:39
• Is this a question or an answer? Jan 26 at 13:55