Ternary Search to find point in in array where the difference is minimum

Question

Let A an array of n positive integers.

How can I find some index k of A such that:

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

have the minimum absolute difference (that is, abs(left - right) is minimum) ?

As the absolute function of this difference is parabolic (decreases until the minimum difference and then increases, like an U ), I heard that Ternary Search is used to find values in functions like this (parabolic), but I don't know how to implement it, since I've searched over the internet and didn't find uses of Ternary Search over parabolic functions.

EDIT: suppose I have all intervals sum in O(1), and I need something faster than O(n) otherwise I wouldn't need Ternary Search..

Answer 1

Let left(k) represent the sum of the values in the array, from A[0] through A[k]. It is trivial to prove that:

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

That it, if you already computed your left for the given k, then left for k+1 is computed by adding the next element to left.

In other words:

If you iterate over the array, from element #0 to element #n-1 (where n is the size of the array), you can compute the running total for left simply by adding the next element in the array to left.

This might seem to be obvious and self-evident, but it helps to state this formally in order for the next step in the process to become equally obvious.

In the same fashion, given right(k) representing the sum of the values in the array starting with element #k, until the last element in the array, you can also prove the following:

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

So, you can find the k with the minimum difference between left(k) and right(k+1) (I'm using a slightly different notation than your question uses, because my notation is more convenient) by starting with the sum total of all values in the array as right(0) and A[0] as left(0), then computing right(1), then, proceed to iterate from the beginning to the array to the end, calculating both left and right on each step, on the fly, and computing the difference between the left and the right values. Finding where the difference is the minimum becomes trivial.

I can't think of any other way to do this, in less than O(n):

1) Computing the sum total of all values in the array, for the initial value of right(0) is O(n).

2) The iteration over the right is, of course, O(n).

I don't believe that a logarithmic binary search will work here, since the values abs(left(k)-right(k)) themselves are not going to be in sorted order.

Incidentally, with this approach, you can also find the minimum difference when the array contains negative values too. The only difference is that since the difference is no longer parabolic, you simply have to iterate over the entire array, and just keep track of where abs(left-right) is the smallest.

Answer 2

Trivial approach:

1. Compute all the sums A[0] + A[1] + ... + A[k] and A[k+1] + A[k+2] + ... + A[n] for any k<=n.
2. Search for the k minimising abs(left - right) for any k<=n

O(n) in space and time.

Edit: Computing all the sums can be done in O(n) with an incremental approach.