Faça Sua Pesquisa.

sábado, 18 de fevereiro de 2012

Binary Search - Procura Binária c++

Neste módulo apresento um código C++ para o algoritmo de pesquisa binária em um array de strings.
O principal objetivo deste algoritmo é procurar um nome dentro de uma lista ordenada.
Se esta lista contiver o nome, o código escreve o nome na tela e retorna seu índice.
O mecanismo de busca se baseia na comparação entre o nome procurado e os nomes contidos no array.
Primeiramente o nome é comparado contra o elemento que se localiza no meio da lista (array) ordenada.
Se o nome procurado é o elemento do meio então o código escreve o nome na tela e retorna seu índice.
Caso contrário se o nome procurado iniciar com uma letra que vem após a letra do elemento do meio, então uma nova pesquisa é realizada somente com os elementos que estão após o meio.
Para isso o código divide novamente os elementos ao meio, e compara contra o elemento central.
Repetindo esse processo até encontrar o nome procurado; divide o array ao meio e compara contra o elemento central.
Agora se na primeira divisão da lista, o elemento procurado for menor que o elemento do meio, ou seja, iniciar com uma letra que vem antes da primeira letra do elemento do meio, então uma nova pesquisa será realizada, repetindo todos procedimentos anteriores, mas desta vez,a pesquisa se dá somente nos elementos da metade superior do array, dividindo-o ao meio novamente e comparando contra o elemento do meio.
#include < iostream.h >
#include < string.h >
typedef char name[32];

name key;

const name Names[] = {"Alisson", "Andre", "Bruno", "Carlos", "Daniel", "Edgar",
"Fabiano", "Gustavo", "Henrique", "Ibson", "Jardel", "Kleber", "Lucas", "Marcio"
, "Nicolas", "Odvan", "Paulo", "Ruy", "Saulo", "Tadeu", "Valdson"};

int BinarySearch(name Key, const name theNames[], int num);

int BinarySearch(name Key, const name theNames[], int num){
int low = 0;
int high = num -1;
while(low<=high){
int midpoint = (low + high)/2;
int result = strcmp(key, theNames[midpoint]);
if (result == 0) {
cout<<"Nome Encontrado";
return midpoint;
}
if(result<0)
high = midpoint -1;
else
low = midpoint + 1;
}
cout << "Nome nao consta na lista";
return -1;
}

int main(){
int num = sizeof(Names)/sizeof(name);
cin >> key;
BinarySearch(key, Names, num);
return 0;
//compilado e testado com sucesso

0 comentários:

Postar um comentário

TecCodigos Copyright © 2011 | Template created by O Pregador | Powered by Blogger