Find

(algorithm)

Definition: An algorithm to select the k^th smallest element of an array and partition the array around it. First, partition around the value of the k^th 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.

Author: PEB

More information

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.

Go to the Dictionary of Algorithms and Data Structures home page.

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