An item that minimizes the amount?

Question

I found a problem that stated:

Let consider a vector x = (x1, x2 ... xn) with real elements. 1). Sort the vector -- easy 2). Find a real number a so that sum ( abs (xi - a) ) is minim 

I don't know if sorting an array helps, but for 2). I thought I could do the arithmetic sum of all the elements in the vector and say that avg is what we were looking for.

But this is not true. Example:

 x = (1, 10, 10) avg = [ 21/3 ] = 7 = a sum = |1 - 7| + |10 - 7| + |10 - 7| = 6 + 3 + 3 = 12 

but if we consider a = 10, we get

 sum = |1 - 10| + |10 - 10| + |10 - 10| = 9 < 12 

Another solution that I could think of would be brute force from the min element to the highest with a step i += 0.1

Answer 1

You are looking for median - not mean.

This is because what you are looking for is actually a geometric environment , which is the standard median if you have only one dimension (and you do it).

The median can be found in O(n) using the Selection Algorithm - so sorting is redundant.