0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Can you explain or provide references explaining what is a double exponential search? I looked it up and couldn't find anything. $\endgroup$ – Simon Zhu May 15 '17 at 8:53
  • $\begingroup$ Just lookup exponential search and infer what double can mean (renamed simultaneous since). $\endgroup$ – Yves Daoust May 15 '17 at 8:56
  • $\begingroup$ 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? $\endgroup$ – Simon Zhu May 15 '17 at 10:22
  • $\begingroup$ @SimonZhu: no, use indexes $k+1-j$ instead of $j$. $\endgroup$ – Yves Daoust May 15 '17 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.