Number of steps of binary search given a stopping criterion

Question

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)$?

• JimN: can you link the paper?
• JimN: Is this search finding a real number (a non-integer number) in the range of [0,n] ?
• Usuario54321: I assume that it is a search for a non-integer number due to the stopping criterion.
• JimN: 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.

Answer 1

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).$$

• user16034: Sorry, $n+1$ was a mistake.