Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Opracował: Piotr DejaVu Szawdyński
Język C++

binary_search

[szablon funkcji] Wykonuje algorytm binarnego przeszukiwania na posortowanym zakresie danych.

Składnia

C/C++
#include <algorithm>

namespace std
{
    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 Compare
    );
}

Argumenty

ArgumentOpis
ForwardIterator FirstIterator postępowy, wskazujący na pierwszy element zakresu do przeszukania.
ForwardIterator LastIterator postępowy, wskazujący na element będący za ostatnim elementem zakresu do przeszukania.
const Type & ValuePoszukiwana wartość.
BinaryPredicate Compare» Dokumentacjabinarny predykat, który określa sposób uporządkowania danych tj. który element jest mniejszy od którego. Predykat ten przyjmuje dwa elementy z zakresu oraz zwraca wartość true, jeśli pierwszy argument powinien znajdować się za drugim, natomiast false w przeciwnym wypadku.

Zwracana wartość

Zwraca true jeżeli szukany element został znaleziony we wskazanym zakresie danych. W przeciwnym wypadku funkcja zwraca wartość false.

Opis szczegółowy

Funkcja wykonuje algorytm binarnego przeszukiwania na posortowanym zakresie danych.

Dane wejściowe muszą być posortowane prawidłowo oraz dostęp do ostatniego elementu danych musi być możliwy poprzez wykonywanie inkrementacji rozpoczynając od iteratora pierwszego elementu.

Funkcja nie modyfikuje danych wejściowych.

Funkcja posiada złożoność obliczeniową logarytmiczną jeżeli przekazane iteratory do funkcji są swobodnego dostępu. W przeciwnym wypadku funkcja posiada złożoność obliczeniową liniową.

Przykład

C/C++
#include <cstdio>
#include <algorithm>
#include <vector>

std::vector < int >& operator <<( std::vector < int >& v, const int & iWartosc )
{
    v.push_back( iWartosc );
    return v;
}

void szukaj( const std::vector < int >& v, const int & iSzukaj )
{
    if( std::binary_search( v.begin(), v.end(), iSzukaj ) )
         printf( "Znaleziono: %d.\n", iSzukaj );
    else
         printf( "Nie znaleziono %d.\n", iSzukaj );
   
}

int main()
{
    std::vector < int > dane;
    dane << 1 << 3 << 5 << 7 << 8 << 9 << 10 << 20 << 50 << 99;
    szukaj( dane, 6 );
    szukaj( dane, 10 );
    szukaj( dane, 15 );
    szukaj( dane, 20 );
    return 0;
}
Standardowe wyjście programu:
Nie znaleziono 6.
Znaleziono: 10.
Nie znaleziono 15.
Znaleziono: 20.

Zagadnienia powiązane

bsearchWykonuje algorytm binarnego przeszukiwania na posortowanej tablicy. (funkcja)

Linki zewnętrzne