# 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`

.