Combien de tours de dichotomie ?

La condition. Après $n$ tours, l'amplitude vaut $\frac{1}{2^n}$. Il faut donc $\frac{1}{2^n}\le 10^{-3}$, c'est-à-dire $2^n\ge 1000$.

Le calcul. $2^9=512<1000$ et $2^{10}=1024\ge 1000$ : il faut $10$ tours.

Pour $10^{-6}$. Il faut $2^n\ge 10^6$. Or $2^{19}=524288$ et $2^{20}=1048576$ : il faut $20$ tours.

Ce qu'il faut retenir. Passer de $10^{-3}$ à $10^{-6}$ ne coûte que $10$ tours de plus. Chaque tour gagne un facteur $2$, donc à peu près un tiers de chiffre décimal : la dichotomie est lente mais elle ne dépend pas de la fonction, et elle n'échoue jamais.