Pesquisa sequencial - I
A técnica de pesquisa sequencial consiste em percorrer a estrutura de dados a partir de seu início até o final ou até a posição onde se encontra a informação procurada. Para exemplificar em um algoritmo, vamos considerar que nossa estrutura de dados a ser pesquisada é um vetor v de inteiros de dimensão 10 e que desejamos buscar um determinado valor K.
algoritmo( )
{
vetor inteiro v[10]; // vetor que contem os dados
inteiro i; // subscritor
inteiro K; // o valor a ser pesquisado
inteiro DIM; // a dimensão do vetor
// atribuição das condições iniciais
DIM := 10;
// leitura dos elementos
para ( i := 1 ate DIM passo 1 )
{
leia ( "elemento: ", v [ i ] );
}
// recebe o valor a ser pesquisado
leia ("informe o valor a ser pesquisado: ", K);
// pesquisa sequencial simples
i := 1;
enquanto ( i <= DIM & v [ i ] <> K )
{
i := i + 1;
}
// resultado
se ( i > DIM )
{
escreva ("nao encontrado");
}
senao
{
escreva ("encontrado na posicao ", i);
}
}
Comentario:
No algoritmo da pesquisa sequencial acima, podemos notar que, a cada iteração do laço enquanto são realizados dois testes de comparação:
1) i <= DIM, para que o subscritor não ultrapasse a dimensão do vetor e
2) V [ i ] <> K, continue no laço até encontrar v [ i ] igual a K.
Desse modo, o número de comparações é o dobro do número de iterações. Fazer uma única comparação a cada iteração é uma forma de otimizar esse algoritmo de busca sequencial. Uma das formas de se conseguir realizar essa otimização é aumentando-se a dimensão do vetor em uma unidade e atribuindo-se a esse novo elemento, o valor de K. Assim está assegurado de que o valor K sempre será encontrado no vetor mas, se o valor de i, o subscritor do vetor, for igual a DIM + 1, na verdade estará significando que o valor K não se encontra entre os elementos do vetor, pois trata-se da última posição.