CKTIS / C++
std::binary_search: sprawdzenie obecności w uporządkowanym zakresie
std::binary_search zwraca wartość logiczną informującą, czy uporządkowany zakres zawiera element równoważny kluczowi.
Wersja: C++23
Składnia
template<class ForwardIt, class T>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template<class ForwardIt, class T, class Compare>
constexpr bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);std::binary_search z <algorithm> bada zakres [first, last) i zwraca true, gdy istnieje element równoważny value według podanego komparatora. Nie zwraca położenia ani liczby duplikatów; do tego służą lower_bound i equal_range.
Warunkiem wstępnym jest partycjonowanie zakresu względem konkretnego klucza dla obu kierunków porównania oraz asymetria: jeśli comp(e, value) jest prawdziwe, comp(value, e) musi być fałszywe. Pełne posortowanie zakresu tym samym spójnym porządkiem jest bezpiecznym warunkiem wystarczającym, ale nie jest konieczne dla pojedynczego klucza. Dopiero naruszenie wymaganej partycji lub asymetrii prowadzi do niezdefiniowanego zachowania. Pusty zakres zwraca false.
Liczba porównań jest logarytmiczna. Dla iteratorów o dostępie losowym także liczba kroków jest logarytmiczna, lecz dla innych iteratorów przemieszczanie może być liniowe. Komparator musi definiować spójny porządek i nie powinien modyfikować elementów.
Przykłady
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array values{1, 3, 5, 7};
std::cout << std::binary_search(values.begin(), values.end(), 5) << '\n';
}
Wynik
1
std::binary_search → 1