First half-probability Grover iterate ($n_{\min }=\max \left\{0,\lceil \frac{\pi }{8\arcsin \sqrt{p}}-\frac{1}{2}\rceil \right\}$)

If the marked fraction is $p$ and $\theta =\arcsin \sqrt{p}$, the success probability after $n$ Grover search algorithm iterations is ${\sin }^2((2n+1)\theta )$. For $0<p\le 1/2$, its first value at least $1/2$ occurs atBefore this integer the angle is below $\pi /4$, so success is below $1/2$. At this integer, the angle lies in $[\pi /4,\pi /4+2\theta )$, contained in $[\pi /4,3\pi /4)$, where squared sine is at least $1/2$. If $p\ge 1/2$, no iteration is needed. For small $p$, $n_{\min }$ is asymptotic to $\pi /(8\sqrt{p})$.