binary_search

Sintaxis:

    #include <algorithm>
    bool binary_search( forward_iterator inicio, forward_iterator fin, const T& val );
    bool binary_search( forward_iterator inicio, forward_iterator fin, const T& val, Comp f );

El algoritmo binary_search() busca un valor val en el rango de elementos __ordenado__ que empieza en inicio y termina en fin, usando búsqueda binaria. El rango de elementos debe estar ordenado acorde al operador <, o a la función predicado f, o de lo contrario la búsqueda no funcionará.

binary_search devuelve un valor true si el elemento val buscado existe en el rango, y false si no existe en el rango.

binary_search en su primera forma requiere que esté definido el operador < para el tipo de datos T, y en su segunda forma que exista la función f con semántica similar a la del operador <. Dos valores a y b son considerados iguales si se cumple !(a<b) && !(b<a).

binary_search() se ejecuta en tiempo logarítmico.

Ejemplo

FIXME traducir.

The following code uses binary_search() to determine if the integers 0-9 are in an array of integers (nums[] should be sorted in ascending order):

   int nums[] = { -242, -1, 0, 5, 8, 9, 11 };
   int start = 0;
   int end = 7;
 
   for( int i = 0; i < 10; i++ ) {
     if( binary_search( nums+start, nums+end, i ) ) {
       cout << "nums[] contains " << i << endl;
     } else {
       cout << "nums[] DOES NOT contain " << i << endl;
     }
   }

When run, this code displays the following output:

   nums[] contains 0
   nums[] DOES NOT contain 1
   nums[] DOES NOT contain 2
   nums[] DOES NOT contain 3
   nums[] DOES NOT contain 4
   nums[] contains 5
   nums[] DOES NOT contain 6
   nums[] DOES NOT contain 7
   nums[] contains 8
   nums[] contains 9

Tópicos Relacionados

equal_range, lower_bound, partial_sort, partial_sort_copy, sort, stable_sort, upper_bound