MÉTODOS DE PESQUISA - PESQUISA SEQUENCIAL

Métodos de Pesquisa:

Pesquisa Sequencial

Introdução

Apresentaremos e discutiremos diferentes estratégias para efetuarmos a pesquisa (busca) de um elemento específico em um conjunto de dados.

Esta operação é muito importante, pois é encontrada com muita frequência em diversas aplicações.

Apresentaremos os métodos de pesquisa sequencial sobre a estrutura de dados de um vetor.

Conceitos

Pesquisa Sequencial sobre Vetores (Arrays)

O que é PESQUISA SEQUENCIAL?

Forma mais simples de realizar pesquisas.

Metodologia: Percorre o vetor, elemento por elemento, verificando se o elemento desejado está presente no vetor.

Pergunta: Quantas comparações são necessárias para achar o elemento 90?

Características

Extremamente simples o algoritmo;

Pode ser muito ineficiente quando o conjunto de dados é muito grande.

Desempenho Computacional

Melhor Caso: é quando é necessário realizar somente uma comparação;

Pior Caso: é quando é necessário realizar n comparações (onde n é o número de elementos);

Caso Médio: é quando é necessário realizar cerca de n/2 comparações.

Exemplo em C

Algoritmo de busca sequencial em um vetor A, com n posições (0 até n − 1), sendo x a chave procurada:

for (i=0; i<n; i++)

if (A[i]==x)

return(i); /*chave encontrada*/

return(-1); /*chave não encontrada*/

Melhorias...

Existem outras maneiras de tornar seu algoritmo mais eficiente.

Usando Sentinelas, que consiste em adicionar um valor x no final da tabela e o sentinela garante que o elemento procurado será encontrado. Melhorando a performance do algoritmo.