binary_search

Статья
06/09/2015

Проверяет, есть в отсортированном диапазоне элемент, равный указанному значению или эквивалентный ему в смысле, заданном двоичным предикатом.

template<class ForwardIterator, class Type> 
   bool binary_search( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value 
   ); 
template<class ForwardIterator, class Type, class BinaryPredicate> 
   bool binary_search( 
      ForwardIterator first,  
      ForwardIterator last, 
      const Type& value,  
      BinaryPredicate comp 
   );

Параметры

first
Прямой итератор, обращающийся к положению первого элемента в рассматриваемом диапазоне.
last
Прямой итератор, обращающийся к положению первого после элемента после последнего в рассматриваемом диапазоне.
value
Значение требуется, чтобы соответствовало значению элемента или, должно соответствовать условию со значением элемента, заданному двоичным предикатом.
comp
Определяемый пользователем объект функции предиката, который определяет, в каком смысле один элемент меньше другого. Двоичный предикат принимает два аргумента и возвращает true, если он удовлетворяется, и false, если не удовлетворяется.

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

Значение true, если элемент найден в диапазоне, который равен или эквивалентен указанному значению; в противном случае — значение false.

Заметки

Сортируемый указанный диапазон источника должен быть допустимым; все указатели должны поддерживать удаление ссылок и до последней позиции должно быть можно добраться от первой путем инкрементного увеличения.

Сортируемый диапазон для каждого расположения вызове функции-члена в приложение алгоритма binary_search в соответствии с тем же заказу, для использования алгоритма для сортировки диапазонами.

Диапазоны источника не меняются binary_search.

Типы значений итераторов пересылки должны быть сравнимы "меньше чем", чтобы можно было их упорядочить. Таким образом, если имеется два элемента, может быть определено, что они равны (ни один не меньше другого) или что один меньше другого. Это приводит к упорядочению неравнозначных элементов

Сложность алгоритма является логарифмической для итераторов с произвольным доступом и линейной в противном случае, с числом шагов, пропорциональным значению (last — first).

Пример

// alg_bin_srch.cpp
// compile with: /EHsc
#include <list>
#include <vector>
#include <algorithm>
#include <functional>      // greater<int>( )
#include <iostream>

// Return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser( int elem1, int elem2 )
{
    if (elem1 < 0)
        elem1 = - elem1;
    if (elem2 < 0)
        elem2 = - elem2;
    return elem1 < elem2;
}

int main( )
{
    using namespace std;

    list <int> List1;

    List1.push_back( 50 );
    List1.push_back( 10 );
    List1.push_back( 30 );
    List1.push_back( 20 );
    List1.push_back( 25 );
    List1.push_back( 5 );

    List1.sort();

    cout << "List1 = ( " ;
    for ( auto Iter : List1 )
        cout << Iter << " ";
    cout << ")" << endl;

    // default binary search for 10
    if( binary_search(List1.begin(), List1.end(), 10) )
        cout << "There is an element in list List1 with a value equal to 10."
        << endl;
    else
        cout << "There is no element in list List1 with a value equal to 10."
        << endl;

    // a binary_search under the binary predicate greater
    List1.sort(greater<int>());
    if( binary_search(List1.begin(), List1.end(), 10, greater<int>()) )
        cout << "There is an element in list List1 with a value greater than 10 "
        << "under greater than." << endl;
    else
        cout << "No element in list List1 with a value greater than 10 "
        << "under greater than." << endl;

    // a binary_search under the user-defined binary predicate mod_lesser
    vector<int> v1;

    for( auto i = -2; i <= 4; ++i )
    {
        v1.push_back(i);
    }

    sort(v1.begin(), v1.end(), mod_lesser);

    cout << "Ordered using mod_lesser, vector v1 = ( " ;
    for( auto Iter : v1 )
        cout << Iter << " ";
    cout << ")" << endl;

    if( binary_search(v1.begin(), v1.end(), -3, mod_lesser) )
        cout << "There is an element with a value equivalent to -3 "
        << "under mod_lesser." << endl;
    else
        cout << "There is not an element with a value equivalent to -3 "
        << "under mod_lesser." << endl;
}

Output

List1 = ( 5 10 20 25 30 50 )
There is an element in list List1 with a value equal to 10.
There is an element in list List1 with a value greater than 10 under greater than.
Ordered using mod_lesser, vector v1 = ( 0 -1 1 -2 2 3 4 )
There is an element with a value equivalent to -3 under mod_lesser.