Definition: Repeatedly check items in an array at random until successful.
Generalization (I am a kind of ...)
search, Las Vegas algorithm.
See also skip list, linear search, binary search.
Note: If any item with a certain value is needed and there are many items with that value, a random search has lower expected time than linear search. If parallel processing is available, random search is fault tolerant (processors may stop working without causing failure) and reasonably efficient.
This definition after Kenneth A. Berman and Jerome L. Paul, Fundamentals of Sequential and Parallel Algorithms, Sect. 18.4, pages 639-640, PWS Publishing Co., Boston, MA, 1996.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 13 November 2008.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "random search", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 13 November 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/randomSearch.html