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$ Commented May 15, 2017 at 8:41
  • $\begingroup$ @YvesDaoust Sorry, they are all positive, yes i should have specified this $\endgroup$ Commented May 15, 2017 at 8:47
  • $\begingroup$ Consider adding that as an update to your post. $\endgroup$ Commented 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$ Commented 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$ Commented May 15, 2017 at 8:53
  • $\begingroup$ Just lookup exponential search and infer what double can mean (renamed simultaneous since). $\endgroup$ Commented 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$ Commented May 15, 2017 at 10:22
  • $\begingroup$ @SimonZhu: no, use indexes $k+1-j$ instead of $j$. $\endgroup$ Commented May 15, 2017 at 10:23

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.