• Pesquisa Binária

O método de pesquisa linear funciona bem com arrays pequenos ou com arrays não ordenados. Entretanto, para arrays grandes a pesquisa linear é ineficiente. Se o array estiver ordenado, a técnica veloz de pesquisa binária pode ser utilizada.

O algoritmo da pesquisa binária elimina metade dos elementos do array que está sendo pesquisado após cada comparação.

Os tremendos ganhos em desempenho da pesquisa binária em relação à linear não são obtidos sem um preço. Classificar a array é uma operação cara.

// pesquisa binária
#include <iostream>
using std::cout;
using std::cin;
using std::endl;

int p_binaria ( const int [], int, int, int, int );

int main()
{
   const int elementos = 10;

   int numeros[ elementos ],
       chave = 0,
       resultado = 0;

   for ( int i=1; i<=elementos; i++ )
      numeros[i] = i;

   cout << "Procurando em array" << endl;
   cout << "Digite um numero de 1 a 10" << endl;
   cin >> chave;

   resultado = p_binaria( numeros, elementos, 0, elementos - 1, chave );

   if ( resultado != -1 )
   {
      cout << "\n" << chave << " encontrado no elemento do array " << resultado << endl;
   }
   else
   {
      cout << "\nElemento nao encontrado" << endl;
   }

   cin;

   return 0;
}

int p_binaria ( const int n[], int total, int primeiro, int ultimo, int chave )
{
    int atual = 0;

   while ( primeiro <= ultimo )
   {
      cout << primeiro << endl << ultimo << endl;
      atual = ( primeiro + ultimo ) / 2;

      if ( chave == n[ atual ] )
         return atual;
      else if ( chave < n[ atual ] )
         ultimo = atual - 1;    // pesquisa metade da array com maiores
      else
         primeiro = atual + 1; // pesquisa metade da array com maiores
    }

return -1; //caso nao ache nada
}

No pior caso, pesquisar um array de 1024 elementos precisará de apenas 10 comparações.

Perguntas??? Email