binary_search

Comprueba si hay un elemento en un intervalo ordenado que sea igual a un valor especificado o que es equivalente a en cierto modo especificado por un predicado binario.

template<class ForwardIterator, class Type>
   bool binary_search(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _Val
   );
template<class ForwardIterator, class Type, class BinaryPredicate>
   bool binary_search(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _Val, 
      BinaryPredicate _Comp
   );

Parámetros

• _First
  Un iterador hacia delante que dirige la posición del primer elemento del intervalo que se buscará.

• _Last
  Un iterador hacia delante que dirige la posición una más allá del último elemento en el intervalo que se buscará.

• _Val
  El valor necesario ser coincidente para el valor de elemento o de que debe satisfacer la condición con el valor del elemento especificado por el predicado binario.

• _Comp
  Objeto definido por el usuario de la función de predicado en el que define sentido que un elemento es menor que otro.Un predicado binario toma dos argumentos y devuelve truecuando se cumple y false cuando no se cumple.

Valor devuelto

true si un elemento se encuentra en el intervalo que sea igual o equivalente al valor especificado; si no, false.

Comentarios

El intervalo de origen ordenada hace referencia debe ser válido; todos los punteros deben ser dereferenceable y, dentro de la secuencia, la posición última debe ser accesible de primera por el aumento.

El intervalo ordenados se debe cada organizar mientras una condición previa a la aplicación del algoritmo de binary_search de acuerdo con el mismo de ordenación que es utilizar el algoritmo para ordenar los intervalos combinados.

los intervalos de origen no son modificados por binary_search.

Los tipos de valor de iteradores hacia delante es necesario que comparable ser secuenciado, para, dadas dos elementos, poder determinar las que son equivalentes (en el sentido de que ninguno es menor que otro) o que uno es menor que otro.Esto produce el orden entre los elementos desiguales

La complejidad del algoritmo es logarítmica para iteradores de acceso aleatorio y lineal de otra manera, con el número de pasos proporcional a (_Last –_First).

Ejemplo

// alg_bin_srch.cpp
// compile with: /EHsc
#include <list>
#include <vector>
#include <algorithm>
#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> L;
   list <int>::iterator Iter;
   bool b1, b2;

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

   L.sort( );

   cout << "L = ( " ;
   for ( Iter = L.begin( ) ; Iter != L.end( ) ; Iter++ )
      cout << *Iter << " ";
   cout << ")" << endl;

   b1 = binary_search( L.begin( ), L.end( ), 10 );
   if  ( b1 )
      cout << "There is an element in list L with a value equal to 10."
           << endl;
   else
      cout << "There is no element in list L with a value equal to 10."
           << endl;
   // a binary_search under the binary predicate greater
   L.sort ( greater<int> ( ) );
   b2 = binary_search( L.begin( ), L.end( ), 10 , greater<int> ( ) );
   if  ( b2 )
      cout << "There is an element in list L with a value equivalent to 10 "
           << "under greater than." << endl;
   else
      cout << "No element in list L with a value equivalent to 10 "
           << "under greater than." << endl;

   // a binary_search under the user-defined binary predicate mod_lesser
   vector <int> v1;
   vector <int>::iterator Iter1;
   int i;
   for ( i = -2 ; i <= 4 ; i++ )
   {
      v1.push_back( i );
   }
   sort ( v1.begin ( ) , v1.end ( ) , mod_lesser );

   cout << "Ordered under mod_lesser, vector v1 = ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")" << endl;

   bool b3 = binary_search( v1.begin( ), v1.end( ), -3 , mod_lesser );
   if ( b3 )
      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;
}

Requisitos

encabezado: <algoritmo>

espacio de nombres: std

Vea también

Referencia

Biblioteca de plantillas estándar