# Number of steps of binary search given a stopping criterion

Reading a paper, I have found an algorithm that uses binary search to find a number between $$0$$ and $$n\in\mathbb{N}$$. The stopping criterion for this binary search is that $$t_2-t_1<\frac{1}{k^2}$$ where $$k>=1$$ is a natural number and $$t_2>t_1$$. Then, it is said that the number of iterations of the binary search is at most $$k\cdot{\text{log}_{2}}(n)$$. Why the number of iterations is $$k\cdot{\text{log}_{2}}(n)$$?

• can you link the paper?
– JimN
May 6, 2023 at 9:21
• Is this search finding a real number (a non-integer number) in the range of [0,n] ?
– JimN
May 6, 2023 at 9:23
• I assume that it is a search for a non-integer number due to the stopping criterion. May 6, 2023 at 9:31
• The statement that it takes $k log(n)$ steps is in the proof of Theorem 7. Compare Theorem 7 to Theorem 1. At the end of the proof of theorem 1, it mentions that a procedure is repeated $k$ times (I believe this is to de-randomize the approximation algorithms and thus making a deterministic algorithm). At the end of the proof of theorem 7, it could be that this $k$ factor in counting the steps of binary search is due to the number of times Algorithm1 is run for the purpose of de-randomization.
– JimN
May 6, 2023 at 10:00

After $$m$$ iterations, the interval size is

$$\frac{t_2-t_1}{2^m}=\frac{n}{2^m}.$$

This becomes smaller than $$k^{-2}$$ when

$$\frac{n+1}{2^m}\le\frac1{k^2}$$

or

$$m\ge\log_2(k^2n)=2\log_2(k)+\log_2(n).$$

• Sorry, $n+1$ was a mistake.
– user16034
May 11, 2023 at 10:27