dddd
2483 palavras
10 páginas
PESQUISA E ORDENAÇÃOVariáveis Compostas Unidimensionais
VETOR
Algoritmos de
Pesquisa
Pesquisa
O problema de procurar (pesquisar) alguma informação numa tabela ou num catálogo é muito comum
Exemplo:
procurar o telefone de uma pessoa no catálogo
procurar o nº da conta de um certo cliente
consultar um determinado saldo em um terminal automático 3
Pesquisa
A tarefa de “pesquisa”, “procura” ou “busca” é, como se pode imaginar, uma função muito utilizada
As rotinas que executam a busca devem ser eficientes (menor tempo possível)
4
Pesquisa
EFICIÊNCIA
O TEMPO GASTO pesquisando dados em tabelas depende do TAMANHO da tabela e do
ALGORITMO utilizado na busca.
5
Algoritmos de Pesquisa
Pesquisa Seqüencial
Pesquisa Seqüencial com Sentinela
Pesquisa Binária
6
Pesquisa Seqüencial
Algoritmo de Pesquisa
Para os algoritmos de pesquisa que se seguem vamos denotar por:
TAB - um vetor contendo N elementos inteiros distintos
DADO - elemento a ser procurado em TAB
ACHOU - indica o sucesso ou falha na pesquisa
POS - aponta para a posição do elemento encontrado 8
Pesquisa Seqüencial
A idéia básica da Pesquisa Seqüencial é localizar o elemento procurado através de comparações sucessivas e seqüenciais, a partir do primeiro elemento do vetor.
A pesquisa termina quando o elemento é encontrado ou quando é atingido o fim do vetor.
No melhor caso, acha-se o elemento procurado na
1a comparação, no pior na Na comparação. Na média, o número de comparações é N/2.
9
Pesquisa Seqüencial
Comparar o elemento procurado (DADO) com cada um dos elementos da tabela TAB na seqüência em que aparecem na tabela
Tabela
Elemento Procurado
3 6 1 2 0
2 2 2 2
2
POS ← 4
10
Pesquisa Seqüencial programa BUSCA1 declarar I {variável de controle}
N {tamanho da tabela},
DADO {elemento a ser