A Pesquisa Sequencial ou Busca Linear
Por: mateusx111 • 26/11/2021 • Pesquisas Acadêmicas • 2.969 Palavras (12 Páginas) • 112 Visualizações
EXERCÍCI0 1
O código abaixo, utiliza um método de pesquisa muito simples, porém é ineficiente quando a quantidade de dados é muito grande, o lado bom é que como ele testa cada valor, os valores não precisam estar ordenados para que o método ache o valor desejado.
/*
Pesquisa Sequencial ou Busca Linear
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int fPesquisa_Sequencial(int *pVetor, int pChave , int pQuantidade);
int main()
{
int TAM = 500;
int vVetor[TAM];
int vAux;
int vChave;
srand(time(NULL));
for (vAux=0; vAux<TAM; vAux++)
{
vVetor[vAux] = rand() % 100; // Preenche todo o vetor aleatóriamente de 0 a 100;
}
printf("\n Digite qual valor voce deseja procurar:");
scanf("%d",&vChave);
if ( fPesquisa_Sequencial(vVetor, vChave , TAM) != -1 )
printf("\n Valor encontrado!\n\n "); // Se a função retornar diferente de -1 então foi encontrado;
else // Senão não foi encontrado;
printf("\n Valor nao encontrado!\n\n ");
system("pause");
}
int fPesquisa_Sequencial(int *pVetor, int pChave , int pQuantidade)
{
int vAux;
for ( vAux=0; vAux < pQuantidade; vAux++ ) // Percorre todo o vetor;
{
if ( pChave == pVetor[vAux] ) // Testa se o valor que está passando é a "chave";
return vAux; // Retorna a posição em que foi encontrado o valor;
}
return -1; // Retorna -1 se não for encontrado;
}
EXERCÍCIO 2
O código com busca binária funciona da seguinte forma:
Seguinte vetor: v = {1, 3, 5, 6, 9, 12, 15, 20, 25}
O valor desejado é 20. O primeiro passo é verificar se elemento desejado é igual, menor ou maior que o elemento do meio do vetor. Se este valor for igual, então o elemento será encontrado. Caso o valor seja menor, todo o resto do vetor que seja maior que este valor será descartado então realizará as buscas somente na metade “menor” do vetor. Caso o valor que desejamos buscar seja maior que o valor do elemento do meio, então o mesmo processo será realizado, porém desta vez será realizado somente as buscas na metade “maior” do vetor, ou seja, a partir do elemento do meio.
Este processo é realizado sucessivamente até que o valor seja encontrado.
Valor do elemento do meio: 9
Valor desejado: 20
Descartado todo o resto do vetor que seja menor ou igual a 9 e continuar as buscas, a partir do 9.
Vetor: 12, 15, 20, 25
Valor do elemento do meio: 15
Valor desejado: 20
Descartar novamente a metade menor do vetor e continuar as buscas:
Vetor: 20, 25
Elemento do meio: 20. Valor encontrado!
#include <stdio.h>
#include <stdlib.h>
int main(){
/* Ponteiro para o vetor que ira ser alocado */
int *v;
/* Tamanho do vetor a ser alocado */
int tamanho_vetor;
/* Variavel de controle dos loops */
int i;
/* Variavel que ira conter o valor temporario da posicao do vetor */
int valor;
/* Variavel que ira conter o elemento a ser pesquisado no vetor */
int pesquisa;
/* Variavel de controle de pesquisa, identifica se o elemento foi encontrado */
int controle_pesquisa = 1;
/* Variaveis de controle do vetor durante a pesquisa binaria */
int inicio, meio, fim;
/* Escreve uma mensagem pedindo o tamanho do vetor */
printf("Digite um tamanho para o vetor: ");
/* Recebe o tamanho do vetor */
scanf("%d", &tamanho_vetor);
/* Aloca o espaco de memoria do vetor */
v = (int *) malloc(tamanho_vetor * sizeof(int));
/* Verifica se houve erro na alocacao de memoria */
if (v == NULL)
{
/* Exibe a mensagem de erro */
printf("Problema ao alocar vetor!");
return(1);
}
else
{
/* Alimentacao do vetor */
for (i = 0; i < tamanho_vetor; i++)
{
printf("Digite a posicao %d do vetor: ", i);
scanf("%d", &valor);
v[i] = valor;
}
/* Recebe o valor a ser pesquisado no vetor */
printf("Digite o elemento que deseja pesquisa no vetor: ");
scanf("%d", &pesquisa);
/* Define o inicio e o fim do vetor. (Fim do vetor: seu_tamanho - 1 */
inicio = 0;
...