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 Black.
Entry modified 13 November 2008.
HTML page formatted Fri Feb 23 10:06:08 2018.
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: https://www.nist.gov/dads/HTML/randomSearch.html