1

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..

Daniel
  • 7,357
  • 7
  • 32
  • 84
  • It seems that the simplest (and possibly optimal) method is a linear search such that one doesn't need to recalculate large sums multiple times. One linear pass calculates the the total sum, which you initialize right with (left is initialized to 0), then with a second linear pass you add A[i] to left and subtract it from right until abs(left-right) starts increasing. Why do you think a ternary search would be better than this simple method? – Ben Hocking Jun 19 '16 at 20:40
  • Ternary Search only makes sense if you have a set of values Sn-1 representing the values |Li - Ri| of some set An. That is, if you have S already. –  Jun 19 '16 at 21:28
  • The algorithm is at https://en.wikipedia.org/wiki/Ternary_search –  Jun 20 '16 at 02:52

2 Answers2

2

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.

Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • I did like you in the first part (to find sums), but I need to find it faster than O(n) and I think it's possible – Daniel Jun 19 '16 at 21:50
  • Calculating the total sum of the values in the array is an O(n) operation. This sets the floor, pretty much, for anything you do going forward, after that. – Sam Varshavchik Jun 19 '16 at 21:53
  • I'm talking about the search complexity only, i need to find the index for minimum difference faster than O(n), cos I'll repeat this a lot – Daniel Jun 19 '16 at 21:59
  • 2
    A binary search on a ***sorted*** array has logarithmic complexity only because, after dividing the search space in half, looking at the dividing value you can determine in which half the searched-for value will be. This requires a ***sorted*** array. Here, the search space is unsorted. You cannot determine, after dividing the search space in half, in which half the searched-for value exists. I don't see how this is mathematically possible. I could be wrong, but I don't think so. – Sam Varshavchik Jun 19 '16 at 22:03
  • the function is unimodal, so its possible to find it faster. I discovered how to. You can use binary search and for each element you look, you ask for the left and for the right one. The smaller of them is the path you follow. If left is bigger, you can forget right path, and so with right. If both have bigger difference than the one you are, you found it. This is like 3*lg(n) – Daniel Jun 20 '16 at 15:17
  • However, for your approach to work, you will need to compute each value in advance, in order to know that given a position `k` what its value is. Which is O(n), a linear iteration. You might as well use the linear iteration to compute the minimum in the manner I outlined. – Sam Varshavchik Jun 20 '16 at 16:06
-1

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.

Lorenzo Belli
  • 1,767
  • 4
  • 25
  • 46
  • in fact, you are computing n sums n times, so time is quadratic – Daniel Jun 19 '16 at 21:51
  • I didn't specified how to do it. Using an incremental methods, for example the one described by @Sam_Varshavchik it's possible to do it in `O(n)` time. – Lorenzo Belli Jun 20 '16 at 07:22