Pesquisa
Ordenação e Pesquisa de Dados
Marco Antonio Montebello Júnior
[email protected]
Pesquisa Seqüencial ou Linear



Varredura serial da tabela
Pode ser aplicada em tabelas representadas por
arrays, arquivos ou listas ligadas
Desempenho do algoritmo de pesquisa
seqüencial é sofrível

NC = (n+1)/2


NC: número de comparações
n: número de elementos da tabela
Obtenção da fórmula
NC = 1 * p1 + 2 * p2 + 3 * p3 + 4 * p4 + ... + n-1 * pn-1 + n * pn
NC = 1 * 1/n + 2 * 1/n + 3 * 1/n + 4 * 1/n + ....+ n * 1/n
NC = 1/n * (1+2+3+4+5+...+n)
NC = 1/n * (n * (n+1) / 2)
NC = (n2 + n) / 2n
NC = (n + 1) / 2

p1, p2, p3, ..., pn = probabilidade de se encontrar o elemento
Técnicas para se melhorar o desempenho do
algoritmo de pesquisa seqüencial





Melhorias por sofisticação no algoritmo
Melhorias baseadas nos dados a serem pesquisados
Sentinela: sentinela nada mais é do que a agregação
do dado que se deseja procurar ao final da tabela sobre
qual se vai executar a pesquisa
Número total de comparações para o pior caso é 2n+1
Uso da sentinela permite fazer uma única comparação
em cada ciclo, reduzindo em 50% o número de
comparações para o pior caso, que passa a ser n+1
Técnicas para se melhorar o desempenho do
algoritmo de pesquisa seqüencial

As principais desvantagens do uso de sentinelas
são:



A necessidade de se alterar a tabela, adicionando um
elemento "estrangeiro" a ela.
A eliminação de uma comparação permite um ganho
muito pequeno de velocidade no programa
O programador deve garantir a presença de uma
posição vazia no final da tabela, não devendo utilizála para nenhum outro propósito (deve-se redobrar a
atenção em operações de inserção).
Algoritmos
 Busca
em tabela
 Busca em tabela melhorado
 Busca com sentinela
 Pesquisa binária
Algoritmo 1:
Busca em tabela



Uma forma intuitiva é construir um algoritmo que
pesquise em todas posições de uma tabela a
ocorrência de um certo elemento procurado.
Isso pode ser realizado por uma estrutura de
repetição do tipo “para até”
Nesse algoritmo percebemos que são executadas n
comparações porque existe comparação até o final,
mesmo o elemento tendo sido encontrado na
primeira posição.
40
1
22
88
13
65
Algoritmo 1:
Busca em tabela
Início
achou  false
para aux  1 até n
se tab[aux] = dado então
achou  true
ind aux
fim_se
fim_para
se achou = true então
escreva “Dado na posição”, ind
senão
escreva “Dado não achado!”
fim_se
fim.
Algoritmo 2:
Busca em tabela melhorado




Uma evolução do algoritmo anterior poderia
contemplar a interrupção da pesquisa, tão logo o
elemento procurado seja encontrado na tabela.
O número de comparações que será realizado
depende da distribuição dos dados na tabela.
Se esta distribuição for aleatória, podemos esperar
que na melhor situação, encontraremos o dado na
primeira posição e na pior situação, teremos que
percorrer toda a tabela, e assim por diante.
Dessa forma, na média o algoritmo executa n/2
repetições da estrutura do tipo “enquanto”
40
1
22
88
13
65
Algoritmo 2:
Busca em tabela melhorado
Início
Achou  false
Procura  true
Ind  0
Enquanto (procura = true) faça
Ind  Ind + 1
Se Ind > n então
Procura  false
Senão
Procura  (tab[ind] <> dado)
Fim_se
Fim_enquanto
Se Ind < = n então
Achou  true
Fim_se
Se (achou = true) então
Escreva “Dado na posição”, Ind
Senão
Escreva “Dado não achado”
Fim_se
Fim.
Algoritmo 3:
Busca com sentinela

O algoritmo tem o seguinte inconveniente:


Para cada valor de “ind” a rotina deve fazer duas
comparações, a primeira para saber se “procura” é
true (verdadeira) e a segunda para testar o valor de
“ind” (ind > n).
Podemos apresentar um algoritmo que realiza a
busca somente com uma única comparação.
Algoritmo 3:
Busca com sentinela



Se soubéssemos que o elemento a ser procurado se
encontra na tabela, não teríamos necessidade de fazer
o teste de fim de tabela, pois, o dado seria encontrado
antes do final.
Uma solução é colocar “dado” no final da tabela, que
deve ser acrescida de uma posição para este fim. Dessa
forma, temos a necessidade de um único teste: o de
comparação com “dado”.
Caso o valor de “ind” seja igual a “n” saberemos que o
elemento procurado não se encontra na tabela.
40
01
22
88
13
65
Dado Procurado
Algoritmo 3:
Busca com sentinela
Início
achou  false
ind  1
tab[n]dado
enquanto (tab[ind] <> dado) faça
Ind  Ind +1
fim_enquanto
achou  (ind <> n)
se (achou = true) então
escreva “Dado na posição”, ind
senão
escreva “Dado não achado!”
fim_se
Fim.
Algoritmo 3:
Busca com sentinela

Agora temos um algoritmo mais eficiente, pois,
com as últimas modificações, o algoritmo
encontra um elemento, na média n/2 pesquisas
e em cada uma delas, executa apenas uma
comparação.
Algoritmo 4:
Pesquisa Binária


Os algoritmos 1, 2 e 3 consideram que a
pesquisa será feita na forma seqüencial e têm a
característica de serem simples, porém, podem
exigir a inspeção de todos os elementos no caso
do elemento procurado não existir na tabela.
A procura binária é uma alternativa, mais
eficiente em relação a procura seqüencial,
exigindo, contudo, que os elementos sobre
os quais a procura será realizada se
encontrem ordenados.
Algoritmo 4:
Pesquisa Binária

Utilizando a procura binária, consideramos em
primeiro lugar o elemento que se encontra no
meio da tabela. Se este elemento é maior que o
elemento que estamos procurando (por “maior”,
entenda-se “aparece depois”), então podemos
garantir que o elemento que estamos procurando
não se encontra na segunda metade da tabela.
Algoritmo 4:
Pesquisa Binária


Repetimos então o processo da procura binária para a
primeira metade da tabela. Se o elemento no meio da
tabela é menor do que o elemento que estamos
procurando (por “menor”, entenda-se “aparece antes”),
então podemos garantir que o elemento que estamos
procurando não se encontra na primeira metade da
tabela. Se o elemento no meio da tabela for igual ao
elemento que estamos procurando, então a procura
termina.
Notamos que em cada passo a procura binária reduz o
número de elementos a considerar para a metade (e daí
o seu nome)
Algoritmo 4:
Pesquisa Binária
Início
Achou  false
Inicio  1
Fim  n
Meio  (1+n) div 2
Enquanto (dado <> tab[Meio] e (Inicio <> Fim) faça
Se (dado > tab[Meio]) então
Inicio  Meio +1
Senão
Fim  Meio
Fim_se
Meio  (Inicio + Fim) div 2
Fim_enquanto
Achou  (dado = tab[meio])
Se (achou = true) então
Escreva “Dado na posição”,meio
Senão
Escreva “Dado não achado!”
Fim_se
Fim
Algoritmo 4:
Pesquisa Binária





Na procura binária somos capazes de reduzir pela metade o
número de elementos a considerar sempre que efetuamos uma
comparação.
Assim, se começarmos com “maxelementos”, o número de
elementos depois de uma passagem é maxelementos/2, depois,
maxelementos/4 e assim, sucessivamente.
No caso geral, o número de elementos depois de n passagens é
maxelementos/2n.
O algoritmo termina quando o número de elementos é menor do
que 1, ou seja, terminamos depois de n passagens se:
 Maxelementos/2n < 1
 Maxelementos < 2n
 log2 maxelementos < n
Dessa forma, para uma tabela com maxelementos, a procura
binária não exige mais do que 1 + log2 maxelementos passagens.
Algoritmo 4:
Pesquisa Binária