Pesquisa sequencial - II
A tecnica de pesquisa sequencial consiste em percorrer a estrutura de dados a partir de seu inicio ate o final ou ate a posicao onde se encontra a informacao procurada. Para exemplificar em um algoritmo, vamos considerar que nossa estrutura de dados a ser pesquisada e um vetor v de inteiros de dimensao 10 e que desejamos buscar um determinado valor K.
algoritmo ( )
{
vetor inteiro v[11]; // vetor que contem os dados
inteiro i; // subscritor
inteiro K; // o valor a ser pesquisado
inteiro DIM; // parametrizar o algoritmo
// atribuição das condições iniciais
DIM := 11;
// leitura dos elementos
para ( i := 1 ate DIM - 1 passo 1 )
{
leia ( "elemento: ", v[i] );
}
// recebe o valor a ser pesquisado
leia ( "informe o valor a ser pesquisado: ", K );
v[11] := K;
// pesquisa sequencial simples
i := 1;
enquanto ( 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, na verdade estará significando que o valor K não se encontra entre os elementos do vetor, pois trata-se da última posição.