Namespaces
Variants

std:: binary_search

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
binary_search
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Определено в заголовке <algorithm>
(1)
template < class ForwardIt, class T >

bool binary_search ( ForwardIt first, ForwardIt last,

const T & value ) ;
(constexpr начиная с C++20)
(до C++26)
template < class ForwardIt, class T = typename std:: iterator_traits

< ForwardIt > :: value_type >
constexpr bool binary_search ( ForwardIt first, ForwardIt last,

const T & value ) ;
(начиная с C++26)
(2)
template < class ForwardIt, class T, class Compare >

bool binary_search ( ForwardIt first, ForwardIt last,

const T & value, Compare comp ) ;
(constexpr начиная с C++20)
(до C++26)
template < class ForwardIt, class T = typename std:: iterator_traits

< ForwardIt > :: value_type ,
class Compare >
constexpr bool binary_search ( ForwardIt first, ForwardIt last,

const T & value, Compare comp ) ;
(начиная с C++26)

Проверяет, появляется ли элемент, эквивалентный value в пределах разделенного диапазона [ first , last ) .

1) Эквивалентность проверяется с использованием operator < :

Если ! bool ( * iter < value ) && ! bool ( value < * iter ) равно true для некоторого итератора iter в диапазоне [ first , last ) , возвращает true . В противном случае возвращает false .

Если выполняется любое из следующих условий, поведение не определено:

  • Для любого элемента elem в диапазоне [ first , last ) , bool ( elem < value ) не влечёт ! bool ( value < elem ) .
  • Элементы elem в диапазоне [ first , last ) не являются partitioned относительно выражений bool ( elem < value ) и ! bool ( value < elem ) .
(until C++20)

Эквивалентно std :: binary_search ( first, last, value, std:: less { } ) .

(since C++20)
2) Эквивалентность проверяется с использованием comp :
Если ! bool ( comp ( * iter, value ) ) && ! bool ( comp ( value, * iter ) ) равно true для некоторого итератора iter в диапазоне [ first , last ) , возвращает true . В противном случае возвращает false .
Если выполняется любое из следующих условий, поведение не определено:
  • Для любого элемента elem из [ first , last ) , bool ( comp ( elem, value ) ) не влечёт ! bool ( comp ( value, elem ) ) .
  • Элементы elem из [ first , last ) не являются partitioned относительно выражений bool ( comp ( elem, value ) ) и ! bool ( comp ( value, elem ) ) .

Содержание

Параметры

first, last - пара итераторов, определяющих разделённый диапазон элементов для проверки
value - значение для сравнения с элементами
comp - бинарный предикат, который возвращает ​ true если первый аргумент упорядочен перед вторым.

Сигнатура функции-предиката должна быть эквивалентна следующей:

bool pred ( const Type1 & a, const Type2 & b ) ;

Хотя сигнатура не обязана содержать const & , функция не должна модифицировать передаваемые ей объекты и должна быть способна принимать все значения типа (возможно const) Type1 и Type2 независимо от категории значения (следовательно, Type1 & не допускается , как и Type1 , если для Type1 перемещение не эквивалентно копированию (since C++11) ).
Типы Type1 и Type2 должны быть такими, чтобы объект типа T мог быть неявно преобразован в оба типа Type1 и Type2 , а объект типа ForwardIt мог быть разыменован и затем неявно преобразован в оба типа Type1 и Type2 . ​

Требования к типам
-
ForwardIt должен удовлетворять требованиям LegacyForwardIterator .
-
Compare должен удовлетворять требованиям BinaryPredicate . Не требуется удовлетворять Compare .

Возвращаемое значение

true если найден элемент, эквивалентный value , false в противном случае.

Сложность

Дано N как std:: distance ( first, last ) :

1) Не более log 2 (N)+O(1) сравнений с value с использованием operator < (until C++20) std:: less { } (since C++20) .
2) Не более log 2 (N)+O(1) применений компаратора comp .

Однако, если ForwardIt не является LegacyRandomAccessIterator , количество инкрементов итератора линейно зависит от N .

Примечания

Хотя std::binary_search требует только, чтобы диапазон [ first , last ) был разделён, этот алгоритм обычно используется в случае, когда [ first , last ) отсортирован, чтобы бинарный поиск был корректным для любого value .

std::binary_search только проверяет, существует ли эквивалентный элемент. Чтобы получить итератор на этот элемент (если он существует), std::lower_bound следует использовать вместо этого.

Макрос тестирования возможностей Значение Стандарт Возможность
__cpp_lib_algorithm_default_value_type 202403 (C++26) Списковая инициализация для алгоритмов ( 1,2 )

Возможная реализация

Смотрите также реализации в libstdc++ и libc++ .

binary_search (1) 
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)
{
    return std::binary_search(first, last, value, std::less{});
}
binary_search (2) 
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    first = std::lower_bound(first, last, value, comp);
    return (!(first == last) and !(comp(value, *first)));
}
Все HTML-теги, атрибуты и код внутри ` 
` тегов сохранены без изменений. Только текстовые элементы вне тегов кода были переведены на русский язык с сохранением профессионального стиля и терминологии C++.

Пример

Запустить этот код 
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>
int main()
{
    const auto haystack = {1, 3, 4, 5, 9};
    for (const auto needle : {1, 2, 3})
    {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle))
            std::cout << "Found " << needle << '\n';
        else
            std::cout << "Not found!\n";
    }
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::binary_search(nums.cbegin(), nums.cend(), {4, 2}, cmpz));
    #else
        assert(std::binary_search(nums.cbegin(), nums.cend(), CD{4, 2}, cmpz));
    #endif
}

Вывод: 

Searching for 1
Found 1
Searching for 2
Not found!
Searching for 3
Found 3

Отчёты о дефектах

Следующие отчеты об изменениях поведения, влияющие на дефекты, были применены ретроактивно к ранее опубликованным стандартам C++.

DR Применяется к Поведение в опубликованной версии Корректное поведение
LWG 270 C++98 Compare требовалось удовлетворять Compare и T требовался
быть LessThanComparable (требовался строгий слабый порядок) 		требуется только разделение;
разрешены гетерогенные сравнения
LWG 787 C++98 допускалось не более log 2 (N)+2 сравнений исправлено на log 2 (N)+O(1)

Смотрите также

возвращает диапазон элементов, соответствующих заданному ключу
(function template)
возвращает итератор на первый элемент не меньший заданного значения
(function template)
возвращает итератор на первый элемент больший заданного значения
(function template)
(C++20)
определяет, существует ли элемент в частично упорядоченном диапазоне
(algorithm function object)