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?

  • 2
    $\begingroup$ What are your thoughts? What attempts have you made? Have you tried working through some examples to see if you can spot any patterns? Have you tried proving your answer to be correct? Have you tried checking whether your algorithm works correctly on some inputs with both negative and positive numbers? You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 28 '18 at 21:30
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 28 '18 at 21:31
  • $\begingroup$ Try working through some examples with small values of $n$ to get a better feeling for what is happening. $\endgroup$ – D.W. Mar 28 '18 at 21:35
  • $\begingroup$ Just simply take $g$ and $l$ to be the maximum and minimum (not of absolute values). $\endgroup$ – xskxzr Mar 29 '18 at 6:57

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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.