# Using std nth element To Find The Median Or Other Quantiles

suggest changeThe `std::nth_element`

algorithm takes three iterators: an iterator to the beginning, *n*th position, and end. Once the function returns, the *n*th element (by order) will be the *n*th smallest element. (The function has more elaborate overloads, e.g., some taking comparison functors; see the above link for all the variations.)

**Note** This function is very efficient - it has linear complexity.

For the sake of this example, let’s define the median of a sequence of length *n* as the element that would be in position ⌈n / 2⌉. For example, the median of a sequence of length 5 is the 3rd smallest element, and so is the median of a sequence of length 6.

To use this function to find the median, we can use the following. Say we start with

std::vector<int> v{5, 1, 2, 3, 4}; std::vector<int>::iterator b = v.begin(); std::vector<int>::iterator e = v.end(); std::vector<int>::iterator med = b; std::advance(med, v.size() / 2); // This makes the 2nd position hold the median. std::nth_element(b, med, e); // The median is now at v[2].

To find the *p*th quantile, we would change some of the lines above:

const std::size_t pos = p * std::distance(b, e); std::advance(nth, pos);

and look for the quantile at position `pos`

.