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.
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?
