Элемент, который минимизирует сумму?

Question

я нашел проблему, которая заявила:

Let's 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 

Я не знаю, если сортировка массива помогает, но 2). я думал, что я могу сделать aritmetic сумму всех элементов в векторе и сказать, что в среднем составляет а мы искали.

Но это неверно. Пример:

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

но если мы рассмотрим = 10 мы получаем

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

Другое решение, которое я мог думать, было бы грубой силы от мин элемента до самого высокого с шагом i += 0.1

Answer 1

Вы ищете median - а не в среднем.

Это потому, что то, что вы ищете, на самом деле является geometric median - это, оказывается, стандартная медиана, если у вас есть только одно измерение (и вы это делаете).

Среднюю величину можно найти в O(n) с использованием Selection Algorithm - поэтому сортировка является избыточной.