binary_search

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

Składnia

#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

Argument	Opis
ForwardIterator First	Iterator postępowy, wskazujący na pierwszy element zakresu do przeszukania.
ForwardIterator Last	Iterator postępowy, wskazujący na element będący za ostatnim elementem zakresu do przeszukania.
const Type & Value	Poszukiwana wartość.
BinaryPredicate Compare	_{» Dokumentacja ♦}binarny 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

#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

bsearch	Wykonuje algorytm binarnego przeszukiwania na posortowanej tablicy. (funkcja)

Linki zewnętrzne

http://www.cplusplus.com/reference/algorithm/binary_search/

Wszystkie teksty są chronione prawami autorskimi. Kopiowanie lub rozpowszechnianie treści poza niniejszym serwisem jest zabronione.

Powyższe ograniczenie nie dotyczy autora opracowania, któremu przysługuje prawo do rozpowszechniania własnego tekstu wedle własnego uznania.