std::binary_search
Актуально для C++23.
#include <algorithm>
Актуально на 2024-03-10.
Define overload #1
template<class ForwardIter, class T>
constexpr bool
binary_search(ForwardIter first, ForwardIter last, const T& val);
template<class ForwardIter, class T>
constexpr bool
binary_search(ForwardIter first, ForwardIter last, const T& val);
template<class ForwardIter, class T> constexpr bool binary_search(ForwardIter first, ForwardIter last, const T& val);
Реализация алгоритма бинарного поиска.
Проверяет есть ли в диапазоне [first, last] значение val.
Диапазон должен быть отсортирован в порядке возрастания.
Вернёт true если val был найден, иначе - false.
Для последовательности из итераторов поддерживающих произвольный доступ, cложность алгоритма log 2(n).
Для последовательности из итераторов НЕ поддерживающих произвольный доступ, cложность алгоритма O(n).
Example, possible implementation
Define overload #2
template<class ForwardIter, class Tp, class Compare>
constexpr bool
binary_search(ForwardIter first, ForwardIter last,
const Tp& val, Compare comp);
template<class ForwardIter, class Tp, class Compare>
constexpr bool
binary_search(ForwardIter first, ForwardIter last,
const Tp& val, Compare comp);
template<class ForwardIter, class Tp, class Compare>
constexpr bool
binary_search(ForwardIter first, ForwardIter last,
const Tp& val, Compare comp);
Реализация алгоритма бинарного поиска.
Проверяет есть ли в диапазоне [first, last] значение val.
Для сравнения используется бинарный предикат "comp".
Диапазон должен быть отсортирован так же, как если бы он был отсортирован с помощью бинарного предиката "comp".
Вернёт true если val был найден, иначе - false.
Для последовательности из итераторов поддерживающих произвольный доступ, cложность алгоритма log 2(n).
Для последовательности из итераторов НЕ поддерживающих произвольный доступ, cложность алгоритма O(n).
Example, possible implementation
Examples
Example 1:
#include <iostream>
#include <algorithm>
int main()
{
auto zxc = {1, 2, 3, 5, 6, 7, 8, 9};
auto it = std::binary_search(std::begin(zxc), std::end(zxc), 4);
std::cout << std::boolalpha << it <<std::endl;
return 0;
}
#include <iostream>
#include <algorithm>
int main()
{
auto zxc = {1, 2, 3, 5, 6, 7, 8, 9};
auto it = std::binary_search(std::begin(zxc), std::end(zxc), 4);
std::cout << std::boolalpha << it <<std::endl;
return 0;
}
#include <iostream>
#include <algorithm>
int main()
{
auto zxc = {1, 2, 3, 5, 6, 7, 8, 9};
auto it = std::binary_search(std::begin(zxc), std::end(zxc), 4);
std::cout << std::boolalpha << it <<std::endl;
return 0;
}
false
false
false
Example 2:
#include <iostream>
#include <algorithm>
int main()
{
auto zxc = {9, 8, 7, 6, 5, 4, 3, 2, 1};
auto it = std::binary_search(std::begin(zxc), std::end(zxc), 4, std::greater{});
std::cout << std::boolalpha << it <<std::endl;
return 0;
}
#include <iostream>
#include <algorithm>
int main()
{
auto zxc = {9, 8, 7, 6, 5, 4, 3, 2, 1};
auto it = std::binary_search(std::begin(zxc), std::end(zxc), 4, std::greater{});
std::cout << std::boolalpha << it <<std::endl;
return 0;
}
#include <iostream>
#include <algorithm>
int main()
{
auto zxc = {9, 8, 7, 6, 5, 4, 3, 2, 1};
auto it = std::binary_search(std::begin(zxc), std::end(zxc), 4, std::greater{});
std::cout << std::boolalpha << it <<std::endl;
return 0;
}
true
true
true
Changelog
C++26
TODOC++23
TODOC++20
TODOC++17
TODOC++14
TODOC++11
TODOSee also
TODO
This page was last modified on 2024-03-10