Pesquisa em Vetores: mudanças entre as edições
| Linha 33: | Linha 33: | ||
O método de busca linear é um tipo de pesquisa em vetores de modo sequencial, isto é, elemento por elemento <ref name="BuscaLinear">http://pt.wikipedia.org/wiki/Busca_linear</ref>. | O método de busca linear é um tipo de pesquisa em vetores de modo sequencial, isto é, elemento por elemento <ref name="BuscaLinear">http://pt.wikipedia.org/wiki/Busca_linear</ref>. | ||
<source lang=" | <source lang="c"> | ||
/** | /** | ||
* Retorna -1 caso não encontre ou a posição, caso encontre. | * Retorna -1 caso não encontre ou a posição, caso encontre. | ||
| Linha 48: | Linha 48: | ||
} | } | ||
</source> | </source> | ||
==Exercícios== | ==Exercícios== | ||
Edição das 12h24min de 3 de setembro de 2014
Pesquisa em Vetores
Os métodos pesquisa vetores consistem em verificar se um elemento pertence a um vetor. Assume-se que os vetores estão ordenados para utilizar os métodos de pesquisa.
Alguns métodos simples e bem conhecidos são:
- Método de pesquisa binária
- Método busca linear
Método de pesquisa binária
O método de pesquisa binária parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor [1].
int PesquisaBinaria ( int vet[], int chave, int Tam)
{
int inf = 0; //Limite inferior (o primeiro elemento do vetor em C é zero )
int sup = Tam-1; //Limite superior (termina em um número a menos 0 à 9 são 10 numeros )
int meio;
while (inf <= sup)
{
meio = (inf + sup)/2;
if (chave == vet[meio])
return meio;
else if (chave < vet[meio])
sup = meio-1;
else
inf = meio+1;
}
return -1; // não encontrado
}
Busca Linear
O método de busca linear é um tipo de pesquisa em vetores de modo sequencial, isto é, elemento por elemento [2].
/**
* Retorna -1 caso não encontre ou a posição, caso encontre.
*/
int procura(char vetor[], int tamanho, char elementoProcurado) {
int i;
for (i = 0; i < tamanho; i++) {
if (vetor[i] == elementoProcurado) {
return i;
}
}
return -1;
}
Exercícios
- Analise o funcionamento de cada um dos algoritmos de ordpesquisa a partir de testes de mesa.
- Implementar e testar os dois algoritmos.
- Pesquise e compare a complexidade de cada algoritmo.
- Construa um programa que recebe dados pelo teclado e os armazene na forma de vetores de 10 posições. Em seguida ordenar e pesquisar se um dado elemento pertence ao vetor.
Referências
--Evandro.cantu (discussão) 20h47min de 2 de setembro de 2014 (BRT)
