Busca Sequencial
Na linguagem C, não temos funções ou métodos prontos para fazermos buscas de valores em um vetor (ou matriz). No caso, precisamos desenvolver uma função que faça a pesquisa do valor em um vetor, a qual será feito elemento por elemento. Uma das grandes vantagens da busca sequencial é que o vetor não precisa estar com seus valores ordenados e é um algorítmo muito simples. O grande problema é caso o vetor seja muito grande, a procura por um elemento pode ser extremamente demorado.
Segue algorítmo que é utilizado na busca sequencial
Referencia: https://pt.wikipedia.org/wiki/Busca_linear, acessado em 05/10/2018
Podemos verificar que é necessário saber de antemão o tamanho do vetor a ser pesquisado e que os valores das posições do vetor estejam carregados (em memória).
Abaixo, temos o seguinte código implementado para podemos fazer pesquisas:
#include stdio.h #include stdlib.h #define tamanho 5 void LeVetor(int vet[]); void ImprimeVetor(int vet[]); int PesquisaSequencial(int v[], int pesq); int main(int argc, char *argv[]) { int vet[tamanho]; int pos, procura; //Lê a vetor LeVetor(vet); printf ("\nDigite um valor para pesquisar: "); scanf("%d",&procura); //Imprime o vetor na tela ImprimeVetor(vet); pos=PesquisaSequencial(vet,procura); if (pos==-1) { printf("\n\nValor nao encontrado no vetor!"); } else { printf("\n\nValor encontrado na posicao %d", pos+1); } printf("\n\n"); system("PAUSE>>NULL"); return 0; } /*----------------------------------- Efetua a leitura do vetor -------------------------------------*/ void LeVetor(int vet[]) { int i; for (i=0;i<tamanho;i++) { printf("Informe o valor %d: ", i+1); fflush(stdin); scanf("%d", &vet[i]); } } /*--------------------------------- Imprime o vetor na tela -----------------------------------*/ void ImprimeVetor(int vet[]) { int i; for (i=0;i<tamanho;i++) { printf("%d\n", vet[i]); } } /*--------------------------------------------------- Busca sequencial -----------------------------------------------------*/ int PesquisaSequencial(int v[], int pesq) { int i; for(i=0;i<tamanho;i++) { if(v[i]==pesq) { return i; } } return -1; // não encontrado }
Busca Binária
A busca binária é outro algoritmos bastante utilizado, e sendo este, é dependente de um vetor ordenado.
O algoritmo precisa de alguns argumentos (além do vetor de elementos ordenados), como o menor e maior valor a ser procurado.
O algoritmo irá procurar a média entre o menor e maior valor e irá comparar se o valor procurado é maior ou menor que a média. O algoritmo mais uma vez irá pegar a média entre o maior ou menor e a média achada, até achar o valor procurado.
Esse método, apesar de ser um pouco mais complexo que a busca sequencial, diminui muito o tempo de procura de valores em grandes vetores.
Segue código:
#include stdio.h #include stdlib.h #define tamanho 5 void LeVetor(int vet[]); void ImprimeVetor(int vet[]); void OrdenaVetor(int v[]); int PesquisaBinaria(int v[], int pesq); int MontaMenu(); int main(int argc, char *argv[]) { int vet[tamanho]; int opcao, pos, procura; //Lê a vetor LeVetor(vet); //Ordena o vetor OrdenaVetor(vet); do { opcao=MontaMenu();//Monta o menu com as opcoes if (opcao==1)//imprime vetor { ImprimeVetor(vet); getch(); } else if (opcao==2)//busca binaria { printf ("\nDigite um valor para pesquisar: "); scanf("%d",&procura); pos=PesquisaBinaria(vet,procura); if (pos==-1) { printf("\n\nValor nao encontrado no vetor!"); } else { printf("\n\nValor encontrado na posicao %d", pos+1); } getch(); } } while (opcao!=0); printf("\n\n"); system("PAUSE>>NULL"); return 0; } /*----------------------------------- Efetua a leitura do vetor -------------------------------------*/ void LeVetor(int vet[]) { int i; for (i=0;i<tamanho;i++) { printf("Informe o valor %d: ", i+1); fflush(stdin); scanf("%d", &vet[i]); } } /*--------------------------------- Imprime o vetor na tela -----------------------------------*/ void ImprimeVetor(int vet[]) { int i; for (i=0;i<tamanho;i++) { printf("%d\n", vet[i]); } } /*--------------------------------------------- Ordena o vetor utilizando o métido Bubble Sort -----------------------------------------------*/ void OrdenaVetor(int v[]) { int i,j,aux; //for (i=0;i<tamanho;i++) for (i=0;i<tamanho-1;i++) { for (j=i+1;j<tamanho;j++) { if (v[i] > v[j]) { aux=v[i]; v[i]=v[j]; v[j]=aux; } } } } /*--------------------------------------------------- Algorítmo de Busca Binária como parâmetro recebe o vetor e o valor a ser procurado -----------------------------------------------------*/ int PesquisaBinaria(int v[], int pesq) { int comeco = 0; //Limite inferior (em C o índice inicial é zero) int final = tamanho-1; //Limite superior (tamanho do vetor -1 // porque o índice inicial é zero ) int meio; while (comeco <= final) { //meio = comeco + (final-comeco)/2; meio = (comeco + final)/2; if (pesq == v[meio]) return meio; else if (pesq < v[meio]) final = meio-1; else comeco = meio+1; } return -1; // não encontrado } //Exibe o menu de opções na tela int MontaMenu() { int opcao; system("cls"); printf("BUSCA BINARIA\n"); printf("_____________\n\n"); printf("Digite a opcao desejada:\n\n"); printf("[1] Ver o vetor ordenado\n"); printf("[2] Pesquisar um valor\n"); printf("[0] Sair\n\n"); printf("Digite a opcao desejada: "); fflush(stdin); scanf("%d", &opcao); return opcao; }