Тернар Поиск, чтобы найти точку в массиве, где разница минимальна

Question

A массив n положительные целые числа.

Как я могу найти индекс к А, что:

left = A[0] + A[1] + ... + A[k] 
right = A[k+1] + A[k+2] + ... + A[n] 

имеют минимальную абсолютную разницу (то есть, abs(left - right) минимальна)?

Поскольку абсолютная функция этой разницы является параболической (уменьшается до минимальной разницы, а затем увеличивается, как U), я слышал, что троичный поиск используется для поиска значений в функциях, как это (параболический), но я не знаю, как его реализовать, так как я искал через Интернет и не нашел использования Тернарного поиска по параболическим функциям.

EDIT: предположим, у меня есть вся сумма интервалов в O (1), и мне нужно что-то быстрее, чем O (N), иначе я бы не нужно Ternary поиск ..

Answer 1

Пусть left(k) представляют собой сумму значений в массиве, от A[0] до A[k]. Это тривиально, чтобы доказать, что:

left(k+1)=left(k)+A[k+1] 

Что, если вы уже вычислен ваш left для данного k, то left для k+1 вычисляется путем добавления следующего элемента в left.

Другими словами:

Если перебрать массив из элемента # 0 в элемент # п-1 (где n является размер массива), можно вычислить нарастающим итогом для left просто добавление следующего элемента в массив к left.

Это может показаться очевидным и само собой разумеющимся, но это помогает сформулировать это формально, чтобы следующий шаг в процессе стал одинаково очевидным.

Таким же образом, не учитывая right(k), представляющий собой сумму значений в массиве, начиная с элемента #k, до последнего элемента в массиве, можно также доказать следующее:

right(k+1)=right(k)-A[k] 

Итак, вы можете найти k с минимальной разницей между left(k) и right(k+1) (я использую несколько отличную нотацию, чем ваш вопрос, потому что мои записи более удобны), начиная с суммы всех значений в массиве как right(0) и A[0] как left(0), затем вычисляет right(1), то, про перейдя с самого начала на массив до конца, вычисляя как left, так и right на каждом шаге «на лету» и вычисляя разницу между левыми и правыми значениями. Найти, где разница является минимальным, становится тривиальным.

Я не могу думать о каком-либо другом способе сделать это, менее чем O(n):

1) Вычисление суммы всех значений в массиве, для начального значения right(0) представляют собой О (п) ,

2) Итерация справа - это, конечно, O (n).

Я не верю, что здесь будет работать логарифмический бинарный поиск, поскольку сами значения не будут отсортированы в порядке сортировки.

Кстати, при таком подходе вы также можете найти минимальную разницу, когда массив содержит отрицательные значения. Единственное различие заключается в том, что, поскольку разница больше не является параболической, вам просто нужно перебирать весь массив и просто отслеживать, где abs(left-right) является самым маленьким.

Answer 2

Trivial подход:

1. Compute все суммы A[0] + A[1] + ... + A[k] и A[k+1] + A[k+2] + ... + A[n] для любого k<=n.
2. Поиск по k минимизируя abs(left - right) для любого k<=n

O(n) в пространстве и времени.

Редактировать: Вычисление всех сумм может быть произведено в O(n) с инкрементным подходом.