(algorithm)
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.
Author: PEB
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 Black.
Entry modified 13 November 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "random search", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 13 November 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/randomSearch.html