Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

Partitioned search range

`std::lower_bound` does not need a fully sorted range: for the given key, all elements that pass its test must come before all elements that fail it.

Version: ISO C++23; implementation support may vary

Syntax

#include <algorithm>

std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);

// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges:  bool(std::invoke(comp, std::invoke(proj, element), key))

A partitioned search range [first, last) groups the results of bool(comp(element, key)) into a true prefix and a false suffix. Either group may be empty, and neither has to be internally sorted. The classic std::lower_bound from <algorithm> returns the first iterator where the test is false, or last if there is none. The result need not equal the key. Calling it on a range that violates the partition precondition is undefined behavior.

The classic comparator overload uses only the element-to-key direction. It can therefore accept a lambda [](const Sale& row, int key) that tests row.sales > key; [] captures nothing. std::ranges::lower_bound (since C++20) accepts an iterator–sentinel pair or a range. It constrains the comparator with indirect_strict_weak_order over the projected elements and key; &Sale::sales lets it compare integers. Both versions need at least forward iterators and use logarithmically many comparisons, but iterator movement can be linear without random access. The range overload returns std::ranges::dangling for a non-borrowed temporary range. Do not dereference an end or invalidated iterator.

std::nth_element and std::partial_sort require random-access iterators and a strict weak ordering: comp(x, x) must be false, and both comparison and equivalence by two false comparisons must be transitive. For integer sales, a.sales > b.sales meets these rules; >= does not. nth_element puts the selected rank in its sorted position and separates the two sides without guaranteeing either side is sorted. partial_sort sorts the requested prefix and leaves the rest in unspecified order. Neither guarantees a partition for an arbitrary key across the whole range. For repeated searches with varying keys, sort the whole range under the same ordering.

Examples

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

struct Sale {
    int sales;
};

int main() {
    const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
    const int key = 90;
    const auto before_key = [](const Sale& row, int key) {
        return row.sales > key;
    };

    const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
    const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);

    if (classic != rows.end() && ranged != rows.end()) {
        std::cout << classic->sales << '\n' << ranged->sales << '\n';
    }
}

Result

70
70

For `90`, both calls print `70`, the first value at or below the threshold, although the range is not sorted in descending order. For `100`, `95` gives false before `120` gives true, so neither call is valid with `100` on this range.

Related lessons

  • C++ · Lesson 23 · Advanced · Version: 3

Sources