CKTIS / C++
Sorting, comparisons, and search ranges
Correct sorting requires a comparator that defines a strict weak ordering. Binary search requires a range partitioned for the relevant condition; sorting the entire range is sufficient but not always necessary.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort from <algorithm> orders the half-open range [first, last) using comp: no later element precedes an earlier one. It requires random-access iterators and elements meeting its move and swap requirements. It performs O(N log N) comparisons. It does not guarantee preservation of the order of equivalent elements; use std::stable_sort for that.
The comparator must define a strict weak ordering. comp(a, b) means that a precedes b, and comp(a, a) must be false. The relation must be transitive. Equivalence, defined as !comp(a, b) && !comp(b, a), must also be transitive and need not match operator==. Do not use <=: it violates the requirement for identical arguments. Failing the comparator requirements invalidates the algorithm's guarantees.
Strict weak ordering and partitioned search ranges are related but distinct requirements. A range partitioned for a predicate has all elements yielding true before all elements yielding false; either part may be empty. For std::lower_bound(first, last, value, comp), that predicate is comp(e, value). The function returns the boundary: the first element yielding false, or last. This does not establish that the searched value is present; do not dereference last.
Sorting with the same ordering ensures this partition for every key. For one key, partitioning alone suffices: [2, 1, 4, 3] satisfies the std::lower_bound precondition for value = 3 and comparison <, despite not being sorted. Other binary-search functions have their own partition requirements. std::lower_bound performs O(log N) comparisons, but without random-access iterators it can take a linear number of iterator steps.
The example sorts integers, then uses the same comp to obtain index 3. The content targets C++23; the supplied reference is an evolving working draft, not a frozen C++23 publication. Compiler and production-runtime support are not attested.
Examples
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 3, 1, 2};
const auto comp = [](int a, int b) { return a < b; };
std::sort(values.begin(), values.end(), comp);
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
std::cout << "index=" << (it - values.begin()) << '\n';
}
Result
1 1 2 3 4 index=3
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.