  Decoherence in quantum searches, and in the Grover search in particular, has
already been extensively studied, leading very quickly to the loss of the
quadratic speedup over the classical case, when searching for some target
(marked) element within a set of size $N$. The noise models used were, however,
global. In this paper we study Grover search under the influence of localized
partially dephasing noise of rate $p$. We find, that in the case when the size
$k$ of the affected subspace is much smaller than $N$, and the target is
unaffected by the noise, namely when $kp\ll\sqrt{N}$, the quadratic speedup is
retained. Once these restrictions are not met, the quadratic speedup is lost.
In particular, if the target is affected by the noise, the noise rate needs to
scale as $1/\sqrt{N}$ in order to keep the speedup. We observe also an
intermediate region, where if $k\sim N^\mu$ and the target is unaffected, the
speedup seems to obey $N^\mu$, which for $\mu>0.5$ is worse than the quantum,
but better than the classical case. We put obtained results for quantum
searches also into perspective of quantum walks and searches on graphs.
