Skip to content

Instantly share code, notes, and snippets.

@lesimoes

lesimoes/capitulo_14_1.c

Created December 29, 2018 21:51
Show Gist options
  • Save lesimoes/49cbe49080f9fca419893871a9ecf978 to your computer and use it in GitHub Desktop.
Save lesimoes/49cbe49080f9fca419893871a9ecf978 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
capitulo_14_1.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TAM 1000000
void gerarVetor(int *vetor){
for(int i = 0; i < TAM ; i ++)
vetor[i] = i + 1;
};
int pesquisaLinear(int *vetor, int valor){
int comp = 0;
for(int i = 0 ; i < TAM ; i ++){
comp++;
if(vetor[i] == valor) break;
}
return comp;
};
int pesquisaLinearBlocos(int *vetor, int inicio, int fim, int valor){
int comp = 0;
for(int i = inicio ; i <= fim ; i ++){
comp++;
if(vetor[i] == valor) break;
}
return comp;
};
int pesquisaIndexada(int *vetor, int valor){
int comp = 0;
if(valor <= vetor[49])
comp = pesquisaLinearBlocos(vetor, 0, 49, valor);
comp = pesquisaLinearBlocos(vetor, 50, TAM, valor);
return comp;
};
int pesquisaBinaria (int *vet, int valor)
{
int comp = 0;
int inf = 0;
int sup = TAM - 1;
int meio;
while (inf <= sup)
{
comp ++;
meio = (inf + sup)/2;
if (valor == vet[meio])
break;
if (valor < vet[meio])
sup = meio-1;
else
inf = meio+1;
}
return comp;
};
int main(){
srand(time(NULL));
int vet[TAM];
gerarVetor(vet);
int buscar = rand() % TAM;
printf("Valor buscado: %d", buscar);
printf(" \nPesquisa Linear - Comparacoes: %d ", pesquisaLinear(vet, buscar));
printf(" \nPesquisa Indexada - Comparacoes: %d ", pesquisaIndexada(vet, buscar));
printf(" \nPesquisa Binaria - Comparacoes: %d ", pesquisaBinaria(vet, buscar));
return 0;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment