selection as important as it issorting is not the only interesting problem dealing with total order relation on set of elements there are number of applications in which we are interested in identifying single element in terms of its rank relative to the sorted order of the entire set examples include identifying the minimum and maximum elementsbut we may also be interested insayidentifying the median elementthat isthe element such that half of the other elements are smaller and the remaining half are larger in generalqueries that ask for an element with given rank are called order statistics defining the selection problem in this sectionwe discuss the general order-statistic problem of selecting the kth smallest element from an unsorted collection of comparable elements this is known as the selection problem of coursewe can solve this problem by sorting the collection and then indexing into the sorted sequence at index using the best comparison-based sorting algorithmsthis approach would take ( log ntimewhich is obviously an overkill for the cases where or (or even or )because we can easily solve the selection problem for these values of in (ntime thusa natural question to ask is whether we can achieve an (nrunning time for all values of (including the interesting case of finding the medianwhere  / prune-and-search we can indeed solve the selection problem in (ntime for any value of moreoverthe technique we use to achieve this result involves an interesting algorithmic design pattern this design pattern is known as prune-and-search or decreaseand-conquer in applying this design patternwe solve given problem that is defined on collection of objects by pruning away fraction of the objects and recursively solving the smaller problem when we have finally reduced the problem to one defined on constant-sized collection of objectswe then solve the problem using some brute-force method returning back from all the recursive calls completes the construction in some caseswe can avoid using recursionin which case we simply iterate the prune-and-search reduction step until we can apply brute-force method and stop incidentallythe binary search method described in section is an example of the prune-and-search design pattern