Definition: An algorithm to select the kth smallest element of an array and partition the array around it. First, partition around the value of the kth element. If the split is not at element k, move the upper or lower boundary and partition again.
See also select and partition, MODIFIND, Select.
Note: This does more swaps than MODIFIND.
C. A. R. Hoare, Algorithm 65, FIND, CACM, 4(7):321, July 1961.
C. A. R. Hoare, Proof of a Program: FIND, CACM, 14(7):39-45, January 1971.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 4 November 2009.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "Find", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 4 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/find.html