Matrizes: Pesquisa sequencial
algoritmo()
{
// pesquisa sequencial I
matriz inteiro V[10];
inteiro i;
inteiro Pesquisado;
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] );
}
// recebendo o valor a ser pesquisado
leia ( "informe o valor a ser pesquisado: ", Pesquisado );
N := 10;
a := 1;
c := 2;
i := 1;
// pesquisando...
enquanto ( i<=N & V[i]<>Pesquisado )
{
i := i + 1;
a := a + 1;
c := c + 2;
}
// verificando se encontrou
se ( i > N )
{
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 exemplifica a técnica de pesquisa sequencial para a busca de valores em uma determinada estrutura de dados. A pesquisa sequencial é a técnica mais simples utilizada para se efetuar a busca de valores em qualquer universo dado de valores. A pesquisa sequencial consiste em percorrer a estrutura a partir do seu inicio até o final ou até a posição onde se encontra a chave procurada.
No exemplo, utilizou-se um vetor de dimensao 10 de tipos numéricos inteiros o qual irá representar a estrutura de dados na qual se deseja efetuar a pesquisa de um valor recebido pelo teclado. Um vetor é uma variável composta unidimensional, logo necessitamos de um índice, e apenas um, para referenciar os seus elementos, tal objetivo é cumprido pela variável i, que tem a função aqui de indexar ou subscritar o vetor V.
Um vetor é também uma variável homogênea, isto é, agrupa valores todos do mesmo tipo sendo que, foi escolhido o tipo inteiro por questões de simplicidade. Na verdade a questão da simplicidade refere-se a entrada dos dados, uma vez que, os mesmos serão recebidos via teclado e, desse modo sua digitação é mais rapida. Foi utilizado a variável N, dispensável no exemplo, e utilizada apenas para tornar o algoritmo mais genérico, por exemplo, se a dimensao do vetor tivesse que ser outra. O valor de N deve ser o mesmo valor da dimensao do vetor em que se deseja efetuar a pesquisa. Então, uma vez recebidos os valores para o vetor V e inicializadas de forma adequada as variáveis i e N tem início o processo da pesquisa sequencial. Conforme explicitado acima, a pesquisa sequencial varre a estrutura de dados desde o seu início (i=1), até o seu final (i<=N) ou até que o valor pesquisado seja encontrado (V[i] <> Pesquisado), quando então também o processo deverá ser encerrado.
O cumprimento dessas duas condições esta garantida pelo laço enquanto enquanto ( i <= N & V[i] <> Pesquisado ). Uma vez finalizado o laço, pelo estouro de uma das condições deve-se testar para verificar qual foi a condição que causou o escape do laço. Isto é feito comparando-se o valor da variável i com o valor limite, no caso a dimensão do vetor N. Se i > N então o valor pesquisado não foi encontrado no vetor V, pois V[N] é o último elemento do vetor e quem causou a saida do laço foi o fato de i tornar-se maior que N rompendo o laço enquanto (i<=N). Por outro lado, se i <= N então quem causou o escape do laço foi o fato de a condição V[i] <> Pesquisado revelar-se falsa, ou seja o vetor V contém pelo menos um elemento igual ao valor que esta sendo pesquisado, e o valor de i neste momento indica a posição desse elemento no vetor V.
No processo acima, podemos notar que para cada iteração do laço enquanto são realizadas duas comparações (i < N e V[i] <> Pesquisado). Supondo então que o valor pesquisado fosse o último elemento do vetor de dimensão N (pior caso) teríamos um total de 2N comparações. Esse valor pode ser diminuido.