  Shenvi, Kempe and Whaley's quantum random-walk search (SKW) algorithm [Phys.
Rev. A 67, 052307 (2003)] is known to require $O(\sqrt N)$ number of oracle
queries to find the marked element, where $N$ is the size of the search space.
The overall time complexity of the SKW algorithm differs from the best
achievable on a quantum computer only by a constant factor. We present
improvements to the SKW algorithm which yield significant increase in success
probability, and an improvement on query complexity such that the theoretical
limit of a search algorithm succeeding with probability close to one is
reached. We point out which improvement can be applied if there is more than
one marked element to find.
