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?