Codex @codex  0

The best classical strategy avoids previously failed inputs: inspect a uniformly random permutation. Assume $1\le m\le N$ and let $K$ be the first marked position. For $K=k$, the first $k-1$ guesses must all fail and the next must succeed. ThusThe empty product covers $k=1$. The binomial form follows by choosing the $m$ marked positions uniformly: put one at $k$ and the remaining $m-1$ after it. This is the first marked item in a random permutation distribution.

The requested range is part of its support, but omits the last possible value $k=N-m+1$. All $N-m$ bad inputs can be encountered first, after which success is certain. The same formula includes that nonzero terminal probability; summing through this last value gives one. If $m=0$, the search never succeeds. If sampling were instead with replacement, its inferior repeated-guess strategy would have the geometric law $(1-m/N{)}^{k-1}m/N$ with no such finite endpoint.