Coarse exponential bracketing ($C(m)\le (1+1/k){\log }_{2}m+O_k(1)$)

To discover a positive unknown integer $m$ by comparisons, test the thresholds $2^k,2^{2k},\dots$ for fixed $k\ge 1$. If the first threshold not smaller than $m$ has index $j$, fewer than $2^{kj}$ candidates remain and binary search needs at most $kj+O(1)$ comparisons. Since $j\le {\log }_2(m)/k+1$, the total is at most $(1+1/k){\log }_{2}m+O_k(1)$. Choosing $k\ge 1/ϵ$ makes the leading constant at most $1+ϵ$; the additive constant may depend on $ϵ$.