Minimization of (z-xi)^2

Question

If I want to find a median (it is equivalent to minimize a function |z - x_i|), I can use the following code snippet:

std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "The median is " << v[v.size()/2] << '\n';

Is there something like this, to find "median" for minimization of (z-x_i)^2? That is, I want to find an element of the array in which the sum of these functions will be minimal.

Answer 1

Given an array x₁, x₂, …, x_n of integers, the real number z that minimizes ∑_{i∈{1,2,…,n}} (z - x_i)² is the mean z* = (1/n) ∑_{i∈{1,2,…,n}} x_i. You want to call std::min_element with a comparator that treats x_i as less than x_j if and only if |n x_i - n z*| < |n x_j - n z*| (we use n z* = ∑_{i∈{1,2,…,n}} x_i to avoid floating-point arithmetic; there are ways to reduce the extra precision required).