CKTIS / C++
std::lower_bound — pierwsza pozycja nie mniejsza od klucza
std::lower_bound wyszukuje granicę w odpowiednio podzielonym zakresie: pierwszy element nie mniejszy od klucza albo koniec zakresu. Zwraca iterator, nie informację o znalezieniu równej wartości.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)std::lower_bound z nagłówka <algorithm> przeszukuje [first, last) i zwraca pierwszy iterator, dla którego comp(*it, value) jest fałszywe, lub last, jeśli takiego elementu nie ma. Bez comp używa domyślnego porównania mniejszości. W rosnącym zakresie liczb wynik wskazuje pierwszy element >= value, także pierwszy spośród duplikatów.
Warunek wstępny to podział względem danego klucza: wszystkie elementy spełniające comp(element, value) muszą poprzedzać pozostałe. Pełne posortowanie zgodnie z tym samym porównaniem wystarcza, ale nie jest konieczne. Naruszenie warunku oznacza niezdefiniowane zachowanie; funkcja nie sortuje danych.
Wynik nie potwierdza obecności klucza. Przed *it sprawdź it != last. W przykładzie z liczbami całkowitymi przed wypisaniem wartości kandydata kod sprawdza tylko it != values.end(); nie porównuje wartości z kluczem. Aby sprawdzić równość, można po wykluczeniu końca zakresu osobno wykonać test *it == key. Dla własnego porządku równoważność oznacza !comp(a, b) && !comp(b, a), niekoniecznie a == b.
Wymagane są co najmniej iteratory jednokierunkowe. Dla N elementów liczba porównań wynosi O(log N), lecz bez iteratorów o dostępie swobodnym liczba kroków iteratora może być liniowa. Przykład używa C++23; podlinkowany dokument jest rozwijanym szkicem standardu, a nie zamrożoną edycją C++23.
Przykłady
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 3, 3, 7};
for (int key : {3, 4, 9}) {
const auto it = std::lower_bound(values.begin(), values.end(), key);
std::cout << key << ": index=" << (it - values.begin());
if (it != values.end()) {
std::cout << ", value=" << *it;
} else {
std::cout << ", end";
}
std::cout << '\n';
}
}
Wynik
3: index=1, value=3 4: index=3, value=7 9: index=4, end
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.