Matrizes: Pesquisa sequencial
algoritmo()
{
matriz inteiro V[11];
inteiro i; // subscritor
inteiro P; // valor a ser pesquisado
inteiro N; // dimensão do vetor
inteiro c; // quantidade de comparações
inteiro a; // quantidade de atribuições
para ( i := 1 ate 10 passo 1 )
{
leia ( "informe valor: ", V[i] );
}
leia ( "informe o valor a ser pesquisado: ", P );
N := 10;
V[N+1] := P;
c := 1;
a := 1;
i := 1;
enquanto ( V[i] <> P )
{
i := i + 1;
a := a + 1;
c := c + 1;
}
se ( i == N + 1 )
{
escreva ( "valor nao encontrado" );
}
senao
{
escreva ( "valor encontrado na posicao ", i );
}
escreva ( "numero de comparacoes: ", c );
escreva ( "numero de atribuicoes: ", a );
}
Comentário
O algoritmo acima otimiza o número de comparações realizadas no laço enquanto durante o processo de pesquisa. Isto é conseguido eliminando-se o teste da condição i<=N do algoritmo anterior e permanecendo apenas o teste enquanto (V[i]<>P). Para garantir que o indexador i não ultrapasse o limite N do vetor V é criado um nó, isto é, declara-se um vetor de dimensão N+1 e utiliza-se a última posição para guardar o valor que se pretende pesquisar. Dessa forma, assegura-se que o valor a ser pesquisado sempre será encontrado, mas somente será válido se for de posição diferente de N+1, pois esse elemento não pertence ao universo dos valores dados. Assim, para o pior caso, aquele em que o valor pesquisado se encontra na última posição do vetor, o número de comparações realizado é N+1. Isto da uma melhoria de desempenho de 50%.