Algorithm for finding the minimum index in array with value exceeding x Given a set $S = \{s_1, \ldots, s_k\}$, find the minimum index $j$ such that $\sum_{i = 1}^j s_i \geq \frac{1}{2}\sum_{i = 1}^k s_i$.

I was reading in a paper about an algorithm for this problem that is described as follows:


  The idea is to construct an array of size $k$, whose $j$th position contains $\sum_{i = 1}^j s_i$. Then one can find the appropriate index $j$ in $O(\log(\min\{j, k - j\}))$ time by using a form of binary search simultaneously from both ends of the array.


Can someone explain how the binary search might work? I know that constructing the array still takes $O(k)$, but I want to use this in an algorithm where the array would be computed just once and used with recursive calls to this algorithm.
Assuming the $s_i$ positive (which wasn't said in the OP), the prefix sum of $s_i$ forms a monotonic sequence.

You can start a simultaneous exponential search from both ends, followed by a standard binary search when the half sum has been crossed. The left exponential search takes $O(\log(j))$ and the right one $O(\log(k-j))$. As they are performed simultaneously, the fastest "wins".