Estimating the range of $1$'s in an array of $0$'s and $1$'s
If c &lt; 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.