How can we construct an algorithm which finds $\mu$ that minimizes $\max | x_i - \mu |$ in a linear time for an array of numbers $[x_1, x_2, \ldots, x_n]$?
I take $g = \max_{i\in \{1,\ldots,n \} } x_i$ and $l = \min_{i\in \{1,\ldots,n \} } x_i$, and $\mu = l + \frac{(g - l)}{2}$
Is it true and why it minimizes the function?
Since $|x| = \max (x, -x)$ for any $x \in \mathbb{R}$, we have $|x_i - \mu| = \max(x_i - \mu, \, \mu - x_i)$. Therefore, $$ \max_i |x_i - \mu| = \max \left(\max_i (x_i - \mu), \, \max_i (\mu - x_i) \right) = \max (g - \mu, \, \mu - l), $$ where $g = \max_i x_i$ and $l = \min_i x_i$. Finally, the function $\max(g - \mu, \mu - l)$ has minimum at $\mu = \frac{l + g}{2}$.
