Passion is like genius; a miracle.

Once given n elements, the Prune-and-search (=Decrease and Conquer) removes a fraction of elements recursively, until the number of elements reaches a predefined threshold. If the threshold is hit, the algorithm performs brute-force searching.

Following is an example of finding the kth smallest value from n elements which demonstrates the idea of prune-and-search.

Algorithm quickSelect(S, k):

Input: Sequence S of n comparable elements, and an integer k which is between 1 and n
Output: The kth smallest elements of S

if n = 1 then
  return the (first) element of S
pick a random element x of S
remove all the elements from S and put them into three sequences
- L, storing the elements in S less than x
- E, storing the elements in S equal to x
- G, storing the elements in S greater than x.

if k <= |L| then
  quickSelect(L, x)
else if k <= |L| + |E| then
  return x
else
  quickSelect(G, k – |L| – |E|)

The time complexity of the algorithm quickSelect is O(n²) in worst case and runs in O(n) expected time.