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

• If the $s_i$ are unconstrained, the prefix sum has no reason to be monotonic and binary search seems unusable. – Yves Daoust May 15 '17 at 8:41
• @YvesDaoust Sorry, they are all positive, yes i should have specified this – Simon Zhu May 15 '17 at 8:47
• Consider adding that as an update to your post. – Yves Daoust May 15 '17 at 8:52
• Could you give a full citation to the paper, please? There may well be relevant information in it that you've missed. – David Richerby May 15 '17 at 9:02

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".
• I mostly get the idea, but for the right exponential search how should I initialize the bound? I think i should initialize to the smallest power of 2 that is larger than the size of $S$, but that means i need to be able to do this in O(log(min{j,k−j})) time, right? – Simon Zhu May 15 '17 at 10:22
• @SimonZhu: no, use indexes $k+1-j$ instead of $j$. – Yves Daoust May 15 '17 at 10:23