title: How to get the equilibrium index of an array in O(n)?
body: <p>I have done a test in C++ asking for a function that returns one of the indices that splits the input vector in 2 parts having the same sum of the elements, for eg: for the <code>vec = {1, 2, 3, 5, 4, -1, 1, 1, 2, -1}</code>, it may return 3, because 1+2+3 = 6 = 4-1+1+1+2-1. So I have done the function that returns the correct answer:</p>
  
  <pre><code>int func(const std::vector&lt; int &gt;&amp; vecIn)
  {
     for (std::size_t p = 0; p &lt; vecin.size(); p++)
     {
        if (std::accumulator(vecIn.begin(), vecIn.begin() + p, 0) == 
            std::accumulator(vecIn.begin() + p + 1, vecIn.end(), 0))
               return p;
     }
     return -1;
  }
  </code></pre>
  
  <p>My problem was when the input was a very long vector containing just 1 (or -1), the return of the function was slow. So I have thought of starting the search for the wanted index from middle, and then go left and right. But the best approach I suppose is the one where the index is in the merge-sort algorithm order, that means: n/2, n/4, 3n/4, n/8, 3n/8, 5n/8, 7n/8... where n is the size of the vector. Is there a way to write this order in a formula, so I can apply it in my function?</p>
  
  <p>Thanks</p>
  
  <hr>
  
  <p><strong>EDIT</strong>
  After some comments I have to mention that I had done the test a few days ago, so I have forgot to put and mention the part of no solution: it should return -1... I have updated also the question title.</p>