Skip to content
C++ Basics: Search Using the Same Sort Rule

C++ Basics: Search Using the Same Sort Rule

November 9, 2026

Use std::binary_search with the comparator that ordered the data. A descending range needs a descending comparison for the search too.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. You need a C++20-capable compiler and standard-library development headers, with g++ on PATH, plus Bash, a text editor, and the mktemp, rm, and rmdir utilities. No third-party library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as binary-search-comparator-equivalence-demo.cpp:

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> levels{9, 7, 7, 2};
    std::cout << std::boolalpha;
    for (int wanted : {7, 8}) {
        std::cout << wanted << " present: "
                  << std::binary_search(levels.begin(), levels.end(), wanted,
                                        std::greater<int>{}) << '\n';
    }
    std::vector<int> empty;
    std::cout << "empty: "
              << std::binary_search(empty.begin(), empty.end(), 7,
                                    std::greater<int>{}) << '\n';
}

Compile and run it. The program runs only after compilation succeeds:

g++ -std=c++20 -Wall -Wextra -Werror -pedantic binary-search-comparator-equivalence-demo.cpp -o binary-search-comparator-equivalence-demo &&
./binary-search-comparator-equivalence-demo

Observed output:

7 present: true
8 present: false
empty: false

Read the result

The descending search finds 7, rejects 8 and returns false for the empty range. Duplicate entries do not change the yes-or-no result.

Apply it carefully

Do not apply an ascending search to descending data. In general, the match is comparator equivalence, meaning neither value compares before the other; it need not mean operator== equality. Use lower_bound or equal_range when you need an iterator or all matching entries. For a linked associative container, prefer its member lookup to avoid linear iterator traversal by a generic algorithm.

The C++ working draft describes the relevant rules. This example uses C++20; the current working draft also includes later additions.

Clean up

Remove only the source and executable created here, then return to the starting directory:

rm -- binary-search-comparator-equivalence-demo.cpp binary-search-comparator-equivalence-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect its remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.

Last updated on