Welcome to Programming and Data Structures

The std::find and std::find_last do linear searches of a container looking for a specific value. There is a std::search which is called with four iterators:

ForwardIt std::search( ForwardIt first, ForwardIt last,
                       ForwardIt s_first, ForwardIt s_last );

It searches for a sequence of values defined by the range [s_first, s_last) within the range [first, last). Thus, we could use it to search for {10, 4, 13} within a vector of integers or a sequence of characters within a string.

There is a std::binary_search which performs a binary search on a sorted range:

bool std::binary_search( ForwardIt first, ForwardIt last,
                         const T& value );

As the name implies, it performs a binary search on a sorted range in \(O(\log n)\) time. But it only returns true or false, indicating whether the value is present in the range. If you want to find the position of the value, you can use std::lower_bound or std::upper_bound that return iterators to the position of the first value not less than (lower bound) or greater than the given value (upper bound), respectively.

Iterator std::lower_bound( ForwardIt first, ForwardIt last,
                            const T& value );

Note that both algorithms return the closest iterator to the value, not a boolean indicating presence. So if you search {5, 10, 15, 20, 25} for 19 using upper_bound you would get an iterator pointing to 15, the first value that is not greater than 19. You would then need to test the value at that location to determine if the exact value you want is present.

The std::sort sorts a range in \(O(n \log n)\) time. The implementation of it usually does not use a single strategy. A common implementation strategy is something known as “introsort” which starts with quicksort and switches to a different strategy when the recursion depth exceeds \(~\log n\text{.}\) (The different strategy is often heapsort, an algorithm we will cover later.) Once a range being sorted in a recursive call gets small enough, it uses insertion sort to finish the job.

This blend of strategies takes advantage of the good constant factors of quicksort, while allowing us to avoid the worst-case \(O(n^2)\) behavior. If we reach \(~\log n\) recursion depth, we might be headed towards the case where we end up recursing all the way down to \(n\) levels of recursion. To avoid that, we switch to heapsort which is guaranteed to only do \(\log n\) levels. Even if we do \(\log n + \log n\) recursive levels, that still is \(O(\log n)\text{.}\)

Once we get to a very small portion of a list, we are no longer concerned about the asymptotic complexity. At that size, insertion sort is often more efficient due to its low overhead and good cache performance.

The sort algorithm is not stable. If you need a stable sort, you can use std::stable_sort which guarantees that the relative order of equal elements is preserved. It tries to allocate a buffer (temporary memory) equal in size to the range being sorted. If it can get that memory, it uses a merge sort algorithm that guarantees \(O(n \cdot \log n)\) performance. If that memory cannot be allocated, it falls back to an in-place sort algorithm that takes \(O(n \cdot \log^2 n)\) time.

To determine if a range is sorted in \(O(n)\) time, you can use the std::is_sorted algorithm.

To partially sort a range, so that the \(n\) smallest elements are sorted and appear at the beginning of the range, you can use the std::partial_sort algorithm. It produces results similar to those produced by only allowing the outer loop of selection sort to run \(n\) times. However, it is generally implemented with a heap sort algorithm for better performance. (\(O(m \log n)\) where \(m\) is the number of things sorted in a total range of \(n\) elements.)

Finally, the standard library exposes various functions that normally are building blocks for search and sort operations, such as std::partition, std::merge, and others, which can be useful in more specialized scenarios.