# Finding a point on the unit segment satisfying certain distance relations from $n$ points

Let $$x_1,x_2,x_3,\dots,x_n$$ be n points on the unit segment $$[0,1]$$.Mathematically it can be shown that there always exists a point $$\in[0,1]$$ such that $$\frac1n \sum_1^n|x-x_i|=\frac12$$. Given $$x_1,x_2,x_3,\dots,x_n$$, how do we find(numerically) $$x$$ satisfying the above relation to given level of accuracy?In other words ,given $$x_1,x_2,x_3,\dots,x_n$$ and $$\epsilon>0$$ ,the task is to find $$x$$ such that $$\Bigg|{\frac1n \sum_1^n|x-x_i|-\frac12}\Bigg| < \epsilon$$.Thank you for any hints/suggestions in advance.

The function $$f(x)= \sum_{i=1}^n |x -x_i|$$ is a piecewise linear continuous function with angles at the points $$x_i$$. Assuming the points are ordered, one can compute successively $$f(0), f(x_1),\cdots ,f(x_n), f(1)$$. It remains to see on which interval the function crosses the value $$\frac{n}{2}$$ and find the intersection point by interpolation on this interval.
The values of the function can be computed efficiently because one has $$$$|x_{k+1} - x_i| - |x_k - x_i| = (x_{k+1}- x_k)([i\le k]-[i > k])$$$$ where $$[]$$ is Iverson's bracket. Hence $$$$f(x_{k+1}) - f({x_k}) = (x_{k+1}-x_k)(k - (n-k)) = (x_{k+1}-x_k)(2k-n)$$$$
The above arguments also shows that $$f(x_k)$$ decreases and reaches its minimum when $$k = \lfloor\frac{n+1}{2}\rfloor$$ then increases. The maximum of $$f$$ is reached at $$x=0$$ or $$x=1$$. In fact one has $$f(0)+f(1) = n$$, so the algorithm could start from $$x=0$$ or from $$x=1$$, depending of which value of $$f$$ is larger than $$n/2$$.