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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 \begin{equation} |x_{k+1} - x_i| - |x_k - x_i| = (x_{k+1}- x_k)([i\le k]-[i > k]) \end{equation} where $[]$ is Iverson's bracket. Hence \begin{equation} f(x_{k+1}) - f({x_k}) = (x_{k+1}-x_k)(k - (n-k)) = (x_{k+1}-x_k)(2k-n) \end{equation}
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$.
