Matrizes: Pesquisa sequencial
algoritmo()
{
// pesquisa sequencial III
matriz inteiro V[11];
inteiro i;
inteiro P;
inteiro N;
inteiro c;
inteiro a;
// recebendo os valores para o vetor V[]
para ( i := 1 ate 10 passo 1 )
{
leia ( "informe valor: ", V[i] );
}
// informando o valor a ser pesquisado
leia ( "informe o valor a ser pesquisado: ", P );
N := 10;
V[N+1] := P;
c := 1;
a := 1;
i := 1;
// fazendo a pesquisa
enquanto ( V[i] <> P )
{
se ( V[i+1] <> P )
{
i := i + 2;
}
senao
{
i := i + 1;
}
c := c + 2;
a := a + 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 sera 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 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%. Esse valor ainda pode ser melhorado fazendo-se o indexador i saltar de 2 em 2 ao invés de 1 em 1. Como podemos ver no algoritmo acima, o número de comparações é equivalente aos casos anteriores mas o número de atribuições do indexador é reduzido a metade o que causa segundo estudos, um aumento de 30% no desempenho da pesquisa.