Laboratório de Algoritmos – Aula 10A

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

BuscaSequencial
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.

buscaBinaria

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;
}
Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s