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?