Known-count search by randomized Grover iteration

Gate model. Use the nonoracle model of One Grover iterate in the standard bit-query model, with exact callable $H$ and $X$ charged per occurrence and an explicitly supplied, costed exact reflection implementation. Each invoked Grover iterate retains its separate standard-bit-query and nonoracle costs.

Input $N=2^n$, exact count $t$, and standard bit-query access to $f=1_M$. If $t=0$, return none without a query. If $t>N\mathrm{/}2$, perform at most nine independent rounds: prepare a fresh address register by $H^{\otimes n}\mathrm{\mid }{0}^n⟩$, measure an address, make one standard bit query to verify it, and return it if marked; after nine failures return the failure symbol.

If $0<t\le N\mathrm{/}2$, find the least positive integer $K$ satisfying $t{K}^2\ge N$ by binary search. Initialize $\mathrm{l}\mathrm{o}=0$ and $\mathrm{h}\mathrm{i}=2^{\lceil n\mathrm{/}2\rceil }$; while $\mathrm{h}\mathrm{i}-\mathrm{l}\mathrm{o}>1$, put $\mathrm{m}\mathrm{i}\mathrm{d}=\mathrm{l}\mathrm{o}+\lceil (\mathrm{h}\mathrm{i}-\mathrm{l}\mathrm{o})\mathrm{/}2\rceil$, replace $\mathrm{h}\mathrm{i}$ by $\mathrm{m}\mathrm{i}\mathrm{d}$ if $t{\mathrm{m}\mathrm{i}\mathrm{d}}^2\ge N$, and otherwise replace $\mathrm{l}\mathrm{o}$ by $\mathrm{m}\mathrm{i}\mathrm{d}$. Set $b$ to the least nonnegative integer with $2^b\ge K$. In each of nine independent rounds, draw $b$ fair bits to obtain $j\in \{0,\dots ,2^b-1\}$. Reject the round without a query if $j\ge K$. Otherwise prepare a fresh $\mathrm{\mid }s⟩=H^{\otimes n}\mathrm{\mid }{0}^n⟩$ and a fresh response qubit $\mathrm{\mid }-⟩$ using $X$ then $H$, apply One Grover iterate in the standard bit-query model exactly $j$ times, measure the address register, and make one separate bit query to verify the measured candidate. Return it if marked. After nine unsuccessful rounds, return the failure symbol. Uniform-state preparation uses exactly $n$ Hadamards; each iterate uses one query and a separately charged reflection. No query, state-preparation, reflection-gate, or classical-bit cost is conflated.