In the quantum search algorithm with a known number of answers $M$ out of a search space of size $N$, it seems that the algorithm works pretty well (though not with pinpoint accuracy) for a fairly wide range of possible known answers. For instance, if the actual number of answers is $M' \in [4/9,4]M$ (for $M$ not too large compared to $N$, then Grover's algorithm optimized for $M$ will give an answer for $M'$ with probability around $1/2$ or better. Since this is a multiplicative interval, it follows that you can find a hit in time $O(\sqrt{N}\cdot \log N)$, which is not bad. In fact, you can get rid of the $\log N$ factor by looking more closely at the $O(\sqrt{N/M})$ running time of standard search.
This is dramatically simpler than the standard method of achieving $O(\sqrt{N})$ run time, which involves phase estimation. (Of course phase estimation is useful in its own right, and the method above only gives one satisfying solution and does not give the number of solutions, which is an interesting problem by itself.) I'm sure I'm not the first to notice this; does it appear somewhere?
I also know I've omitted many details, like what to do when $M$ is not very small compared to $N$. It's also worth noting that there are many examples (like hash collisions) where you have a good idea what $M$ will be without knowing its exact value.
