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 é um tipo de pesquisa em vetores de modo sequencial, isto é, elemento por elemento .

/**
 * 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 ordpesquisa a partir de testes de mesa.
2. Implementar e testar os dois algoritmos.
3. Pesquise e compare a complexidade de cada algoritmo.
4. Construa um programa que recebe dados pelo teclado e os armazene na forma de vetores de 10 posições. Em seguida ordenar e pesquisar se um dado elemento pertence ao vetor.

Referências

---

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

---