I have a large array $A$ that contains something like $[0..1..0..]$. It has a continuous range of $0$'s, followed by a range of $1$'s, and then another range of $0$'s.

This array is large and access is expensive, so I want to use a sampling algorithm to estimate the range $(i, j)$, where $A_i$ is the first $1$ and $A_j$ is the last $1$. Let's say I want to approximate this within an error of $\epsilon n$ where $n$ is the size of $A$, so that I get a range $(i', j')$ where $|i' - i| \leq \epsilon n$ and $|j' - j| \leq \epsilon n$.

What is an algorithm I can use to achieve this?


If c < 0.5 then this can't be done faster than O(n). Assume the array is all zeroes, with a single 1 somewhere in the middle. You have to examine array elements at least until you find the 1, or until you are left with an unexamined subarray of size 2cn. Since you have no clue where the 1 is, it might take n attempts to find a 1, and n - 2cn attempts until you can give a result with an error less than cn in i and j. (If you are left with an interval of size 2cn you just let i = j = middle of the interval).

Obviously if c >= 0.5 then you can let i = j = n/2, and the error is less than cn whatever the correct values are.

| cite | improve this answer | |

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.