Choose a "middle" point from a set
For a point $x$, let $d(x)$ be the sum of distances between $x$ and points in $A$. For $x \notin A$, the derivative $d'(x)$ has the nice formula
$$ d'(x) = |\{y \in A : y &lt; x\}| - |\{y \in A : y &gt; x\}|. $$
This shows why the median is the best answer when you don't have to select a point from $A$. For a point $x \in A$, $d(x)$ is the same as your objective function, hence the solution is to choose the median. You can find the median in linear time, as described in Wikipedia and various other resources.