03_algorithms_05_divide.tex

\section{Divide and conquer}

Divide and conquer algorithms offer a great mix of performance and functionality.

While we can utilize hash-based containers to lookup any specific element in $O(1)$ amortized time, this approach has two drawbacks. Firstly, we can only look up a specific element; if that element is not present in the container, we get a simple lookup failure. Secondly, our type must be hashable, and the hash function must be reasonably fast.

Divide and conquer algorithms allow the lookup of bounds based on strict weak ordering and work even when the container’s specific value is not present. Additionally, since we are working with a sorted container, we can easily access neighbouring values once we have determined a boundary.

\subsection{\texorpdfstring{\cpp{std::lower_bound}, \cpp{std::upper_bound}}{\texttt{std::lower\_bound}, \texttt{std::upper\_bound}}}
\index{\cpp{std::lower_bound}}
\index{\cpp{std::upper_bound}}

The \cpp{std::lower_bound} and \cpp{std::upper_bound} algorithms offer boundary search with logarithmic complexity (for random access ranges.

\cppversions{\texttt{lower\_bound}}{\CC98}{\CC20}{N/A}{\CC20}
\cppversions{\texttt{upper\_bound}}{\CC98}{\CC20}{N/A}{\CC20}
\constraints{\texttt{forward\_range}}{}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

\noindent The two algorithms differ in which bound they return:

\begin{itemize}
    \item the \cpp{std::lower_bound} returns the first element for which \texttt{elem < value} returns false (i.e. first element for which \texttt{elem >= value})
    \item the \cpp{std::upper_bound} returns the first element for which \texttt{value < elem}
    \item if no such element exists, both algorithms return the end iterator
\end{itemize}

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/cbz464eWe}{\ExternalLink}}
\footnotesize Example of using \cpp{std::lower_bound} and \cpp{std::upper_bound} to divide a sorted range into three parts: lower than the bottom threshold, between the bottom and upper threshold and higher than the upper threshold.
\tcblower
\cppfile{code_examples/algorithms/lower_bound_code.h}
\end{codebox}

While the algorithms will operate on any \cpp{forward_range}, the logarithmic divide and conquer behaviour is only available for \cpp{random_access_range}. Data structures like \cpp{std::set}, \cpp{std::multiset}, \cpp{std::map} and \cpp{std::multimap} offer their $O(logn)$ implementations of lower and upper bound as methods.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/o9Wdvzno9}{\ExternalLink}}
\footnotesize Example of using \cpp{lower_bound} and \cpp{upper_bound} methods on a \cpp{std::multiset}.
\tcblower
\cppfile{code_examples/algorithms/lower_bound_set_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::equal_range}}{\texttt{std::equal\_range}}}
\index{\cpp{std::equal_range}}

The \cpp{std::equal_range} algorithm returns both lower and upper bounds for the given value.

\cppversions{\texttt{equal\_range}}{\CC98}{\CC20}{N/A}{\CC20}
\constraints{\texttt{forward\_range}}{}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

Because the lower bound returns the first element for which \texttt{elem >= value} and the upper bound returns the first element for which \texttt{value < elem}, the result is a range \texttt{[lb, ub)} of elements equal to the value.

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/bhW73YG1b}{\ExternalLink}}
\footnotesize Example of using \cpp{std::equal_range}.
\tcblower
\cppfile{code_examples/algorithms/equal_range_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::partition_point}}{\texttt{std::partition\_point}}}
\index{\cpp{std::partition_point}}

Despite the naming, \cpp{std:partition_point} works very similarly to \texttt{std::upper\-\_bound}, however instead of searching for a particular value, it searches using a predicate.

\cppversions{\texttt{partition\_point}}{\CC11}{\CC20}{N/A}{\CC20}
\constraints{\texttt{forward\_range}}{}{N/A}{\texttt{unary\_predicate}}

\cpp{std::partition_point} will return the first element that does not satisfy the provided predicate. This algorithm only requires the range to be partitioned (with respect to the predicate).

\begin{codebox}[]{\href{https://compiler-explorer.com/z/WTzs4zYTq}{\ExternalLink}}
\footnotesize Example of using \cpp{std::partition_point}.
\tcblower
\cppfile{code_examples/algorithms/partition_point_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::binary_search}}{\texttt{std::binary\_search}}}
\index{\cpp{std::binary_search}}

The \cpp{std::binary_search} provides a presence check, returning a boolean indicating whether the requested value is present in the sorted range or not.

\cppversions{\texttt{binary\_search}}{\CC98}{\CC20}{N/A}{\CC20}
\constraints{\texttt{forward\_range}}{}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

Using \cpp{std::binary_search} is equivalent to calling \cpp{std::equal_range} and checking whether the returned is non-empty; however, \cpp{std::binary_search} offers a single lookup performance, where \cpp{std::equal_range} does two lookups to determine the lower and upper bounds.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/7fP71Kjvx}{\ExternalLink}}
\footnotesize Example of using \cpp{std::binary_search} with an equivalent check using \cpp{std::equal_range}.
\tcblower
\cppfile{code_examples/algorithms/binary_search_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{bsearch} - C standard library}{\texttt{bsearch} - C standard library}}
\index{\cpp{bsearch}}

From the C standard library, C++ inherits \cpp{bsearch}. This algorithm returns one of the elements equal to the provided key, or \cpp{nullptr} if none such element is found.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/sEEashheY}{\ExternalLink}}
\footnotesize Example of using \cpp{bsearch}.
\tcblower
\cppfile{code_examples/algorithms/bsearch_code.h}
\end{codebox}

As with \cpp{qsort}, there is effectively no reason to use \cpp{bsearch} in C++ code. Depending on the specific use case, one of the previously mentioned algorithms should be a suitable replacement.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/9ePnd7vGc}{\ExternalLink}}
\footnotesize Example demonstrating alternatives to \cpp{bsearch}.
\tcblower
\cppfile{code_examples/algorithms/bsearch_alternatives_code.h}
\end{codebox}