Question

Como eu faria uma busca Binaria otimizada em C ou C++? Os retornos devem fazer sentido.

Answer 1

Detalhes:

Implementação da busca em C++, passando um vector<int> e o numero a ser buscado, e retornando sua posição

Código:

#include<vector>

#define NOT_FOUND -1

int binarySearch(vector<int> * v, int x){

 int left = 0;

 int right = v->size()-1;

 while(left <= right){

   int mid = (right+left)/2;

   if(v->at(mid) == x) return mid;

   if(v->at(mid) > x) right = mid - 1;

   else left = mid + 1;

 }

 return NOT_FOUND;

}

Answer 2

//Implementação Iterativa:

int PesquisaBinaria (int vet[], int chave, int Tam)

{

    int inf = 0;     // limite inferior (o primeiro índice de vetor em C é zero          )

    int sup = Tam-1; // limite superior (termina em um número a menos. 0 a 9 são 10 números)

    int meio;

    while (inf <= sup)

    {

         meio = (inf + sup)/2;

         if (chave == vet[meio])

              return meio;

         if (chave < vet[meio])

              sup = meio-1;

         else

              inf = meio+1;

    }

    return -1;   // não encontrado

}

//Implementação Recursiva:

// x => chave | v[] => vetor ordenado | e => limite inferior (esquerda) | d => limite superior (direita)

int PesquisaBinaria (int x, int v[], int e, int d)

{

int meio = (e + d)/2;

if (v[meio] == x)

   return meio;

if (e >= d)

   return -1; // não encontrado

else

    if (v[meio] < x)

       return PesquisaBinaria(x, v, meio+1,      d);

    else

       return PesquisaBinaria(x, v,      e, meio-1);

}