LA – Ling C – Aula 10A – Busca Sequencial e Binaria

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