binary_search

Článek
06/09/2015

Ověřuje, zda existuje prvek v seřazené oblasti, který je roven zadané hodnotě nebo je jí rovnocenný ve smyslu podle binárního predikátu.

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 
   );

Parametry

first
Dopředný iterátor, který adresuje umístění prvního prvku v oblasti pro hledání.
last
Dopředný iterátor, který adresuje umístění jedno místo za posledním prvkem v oblasti pro hledání.
value
Hodnota požadovaná k porovnání s hodnotou elementu nebo která musí splňovat podmínku s hodnotou elementu zadanou binárním predikátem.
comp
Objekt funkce predikátu definovaný uživatelem, který definuje smysl, ve kterém jeden prvek je menší než jiný.Binární predikát přijímá dva argumenty a vrátí hodnotu true, když vyhovují, a hodnotu false, pokud nevyhovují.

Vrácená hodnota

true Pokud je nalezen element v rozsahu, který je rovný nebo ekvivalentní konkrétní hodnotě hodnotu; jinak false.

Poznámky

Odkazovaný seřazený zdrojový rozsah musí být platný; u všech ukazatelů musí být možné zrušit referenci a poslední pozice musí být dosažitelná z první pomocí přírůstků.

Podmínkou použití algoritmu binary_search ve stejném pořadí, jaké používá algoritmus k seřazení kombinovaných rozsahů, je, aby byl seřazený rozsah uspořádán.

Zdrojové rozsahy nejsou prostřednictvím binary_search změněny.

Typy hodnot iterátorů předání musí být menší než srovnatelná s hodnotou příkazu, to znamená, že když jsou uvedeny dva elementy, může být stanoveno, že jsou ekvivalentní (v tom smyslu, že ani jeden není menší než ten druhý) nebo že jeden je menší než druhý.To má za výsledek řazení mezi neekvivalentními prvky

Složitost algoritmu je logaritmický pro iterátory s náhodným přístupem a v opačném případě lineární, přičemž počet kroků je přímo úměrný (last – first).

Příklad

// 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;
}

Výsledek

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.