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

Question

Пусть A массив из n натуральных чисел.

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

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

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

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

РЕДАКТИРОВАТЬ: предположим, что у меня есть сумма всех интервалов в O(1), и мне нужно что-то быстрее, чем O(n), в противном случае мне не нужен троичный поиск..

Answer 1

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

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

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

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

Если вы перебираете массив, от элемента #0 до элемента #n-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) является O (n).

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

Я не верю, что логарифмический двоичный поиск будет работать здесь, так как значения abs(left(k)-right(k)) Сами по себе не будут в отсортированном порядке.

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

Answer 2

Тривиальный подход:

1. Подсчитать все суммы 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) с постепенным подходом.