Pesquisa em Vetores

Pesquisa em Vetores

Os métodos pesquisa vetores consistem em verificar se um elemento pertence a um vetor. Assume-se que os vetores estão ordenados para utilizar os métodos de pesquisa.

Alguns métodos simples e bem conhecidos são:

• Método de pesquisa binária;
• Método busca linear.

Método de pesquisa binária

O método de pesquisa binária parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor .

int PesquisaBinaria ( int vet[], int chave, int Tam)
{
     int inf = 0; //Limite inferior      (o primeiro elemento do vetor em C é zero          )
     int sup = Tam-1; //Limite superior    (termina em um número a menos 0 à 9 são 10 numeros )
     int meio;
     while (inf <= sup) 
     {
          meio = (inf + sup)/2;
          if (chave == vet[meio])
               return meio;
          else if (chave < vet[meio])
               sup = meio-1;
          else
               inf = meio+1;
     }
     return -1;   // não encontrado
}

Busca Linear

O método de busca linear é uma pesquisa sequencial em um vetor, isto é, elemento por elemento. Se o vetor estiver ordenado, este no é o método mais eficiente, no caso é melhor usar a busca binaria .

/**
 * Retorna -1 caso não encontre ou a posição, caso encontre.
 */
 int procura(char vetor[], int tamanho, char elementoProcurado) {
     int i;
     for (i = 0; i < tamanho; i++) {
         if (vetor[i] == elementoProcurado) {
             return i;
         }
     }

     return -1;
 }

Exercícios

1. Analise o funcionamento de cada um dos algoritmos de pesquisa.
2. Implementar e testar os dois algoritmos.
3. Construa um programa que recebe dados pelo teclado e os armazene na forma de vetores de 10 posições. Em seguida pesquisar se um dado elemento pertence ao vetor usando o método de pesquisa sequencial.
4. Para testar o método de busca binária o vetor deve primeiramente ser ordenado.
5. Construa um programa que receba strings pelo teclado e os armazene na forma de vetores de 10 posições. Depois, modifique um dos algoritmos de ordenamento para que o ordenar os strings armazenados no vetor em ordem alfabética.
6. Construa um programa que receba nomes de pessoas de um arquivo de texto, um nome cada linha, e em seguida armazene os nomes ordenados em ordem alfabética em outro arquivo.

   Pesquise e use as funções:

fopen(ARQUIVO, MODO);
fgets(STRING,TAMANHO,ARQUIVO);

Referências

---

--Evandro.cantu (discussão) 20h47min de 2 de setembro de 2014 (BRT)

---