You can straightaway know that we need to divide the voltages in range but what would be a good range?
Suppose our each interval range is m, and total length is n, then in the worst case we would look at (n/m) intervals and for the last interval we might need to do a linear search upto the end of the interval. So our cost function, let call it f(m) would be:
We can find out by differentiating that this function achieves minimum value at m=sqrt(n) and the minima is less than 1000. Since we are not asked to minimize the cost but to achieve an answer in cost < 1000, we can use different ranges as well. I tried the value of m as 400, 500, 600 all of which worked.
Most people find that this sqrt(n) was intuitive and I would agree but still proof is better.