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.

Improve this question
$\endgroup$
4
  • $\begingroup$ If the $s_i$ are unconstrained, the prefix sum has no reason to be monotonic and binary search seems unusable. $\endgroup$
    – user16034
    May 15, 2017 at 8:41
  • $\begingroup$ @YvesDaoust Sorry, they are all positive, yes i should have specified this $\endgroup$
    – Simon Zhu
    May 15, 2017 at 8:47
  • $\begingroup$ Consider adding that as an update to your post. $\endgroup$
    – user16034
    May 15, 2017 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, 2017 at 9:02

1 Answer 1

Reset to default
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".

Improve this answer
$\endgroup$
4
  • $\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, 2017 at 8:53
  • $\begingroup$ Just lookup exponential search and infer what double can mean (renamed simultaneous since). $\endgroup$
    – user16034
    May 15, 2017 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, 2017 at 10:22
  • $\begingroup$ @SimonZhu: no, use indexes $k+1-j$ instead of $j$. $\endgroup$
    – user16034
    May 15, 2017 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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