Pesquisa em Vetores: mudanças entre as edições
De Wiki Cursos IFPR Foz
Ir para navegaçãoIr para pesquisar
| (4 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
| Linha 3: | Linha 3: | ||
Alguns métodos simples e bem conhecidos são: | Alguns métodos simples e bem conhecidos são: | ||
*Método de pesquisa binária | *Método de pesquisa binária; | ||
*Método busca linear | *Método busca linear. | ||
==Método de pesquisa binária== | ==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 <ref name="PesquisaBinária">http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria</ref>. | 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 <ref name="PesquisaBinária">http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria</ref>. | ||
<source lang="c"> | <source lang="c"> | ||
| Linha 31: | Linha 31: | ||
==Busca Linear== | ==Busca Linear== | ||
O método de busca linear é | O método de '''busca linear''' é uma pesquisa sequencial em um vetor, isto é, elemento por elemento. Se o vetor estiver ordenado, este no é o método mais eficiente, no caso é melhor usar a busca binaria <ref name="BuscaLinear">http://pt.wikipedia.org/wiki/Busca_linear</ref>. | ||
<source lang="c"> | <source lang="c"> | ||
| Linha 50: | Linha 50: | ||
==Exercícios== | ==Exercícios== | ||
#Analise o funcionamento de cada um dos '''algoritmos de | #Analise o funcionamento de cada um dos '''algoritmos de pesquisa'''. | ||
#'''Implementar''' e '''testar''' os dois algoritmos. | #'''Implementar''' e '''testar''' os dois algoritmos. | ||
#Construa um '''programa''' que recebe dados pelo teclado e os armazene na forma de '''vetores''' de 10 posições. Em seguida pesquisar se um dado elemento pertence ao vetor usando o método de pesquisa sequencial. | |||
#Construa um '''programa''' que recebe dados pelo teclado e os armazene na forma de '''vetores''' de 10 posições. Em seguida | #Para testar o método de busca binária o vetor deve primeiramente ser ordenado. | ||
#Construa um programa que receba strings pelo teclado e os armazene na forma de vetores de 10 posições. Depois, modifique um dos algoritmos de ordenamento para que o ordenar os strings armazenados no vetor em ordem alfabética. | |||
#Construa um programa que receba nomes de pessoas de um arquivo de texto, um nome cada linha, e em seguida armazene os nomes ordenados em ordem alfabética em outro arquivo. | |||
#:Pesquise e use as funções: | |||
fopen(ARQUIVO, MODO); | |||
fgets(STRING,TAMANHO,ARQUIVO); | |||
==Referências== | ==Referências== | ||
Edição atual tal como às 00h43min de 10 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 é uma pesquisa sequencial em um vetor, isto é, elemento por elemento. Se o vetor estiver ordenado, este no é o método mais eficiente, no caso é melhor usar a busca binaria [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 pesquisa.
- Implementar e testar os dois algoritmos.
- Construa um programa que recebe dados pelo teclado e os armazene na forma de vetores de 10 posições. Em seguida pesquisar se um dado elemento pertence ao vetor usando o método de pesquisa sequencial.
- Para testar o método de busca binária o vetor deve primeiramente ser ordenado.
- Construa um programa que receba strings pelo teclado e os armazene na forma de vetores de 10 posições. Depois, modifique um dos algoritmos de ordenamento para que o ordenar os strings armazenados no vetor em ordem alfabética.
- Construa um programa que receba nomes de pessoas de um arquivo de texto, um nome cada linha, e em seguida armazene os nomes ordenados em ordem alfabética em outro arquivo.
- Pesquise e use as funções:
fopen(ARQUIVO, MODO); fgets(STRING,TAMANHO,ARQUIVO);
Referências
--Evandro.cantu (discussão) 20h47min de 2 de setembro de 2014 (BRT)
