dddd

Páginas: 10 (2483 palavras) Publicado: 13 de novembro de 2014
PESQUISA E ORDENAÇÃO
Variá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


PesquisaSeqü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çãodo 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 Nacomparaçã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 serprocurado na tabela},
POS {posição em que se encontra o elemento}
:inteiros
ACHOU {valor lógico que representa o suceso da busca}:lógica
TAB {tabela a ser consultada} vetor com no máximo 30 elementos inteiros
início
solicitar a entrada do tamanho da tabela, ler (N)
solicitar a entrada dos dados da tabela
para I de 1 até N faça
ler ( TAB[I] )
fim para
solicitar a entrada do elemento a serprocurado, ler(DADO)
11

ACHOU ←falso
para I de 1 até N faça
se TAB[I] = DADO
então
ACHOU ← verdadeiro
POS ← I

Pesquisa Seqüencial

fim-se
fim para
se ACHOU
então escrever (DADO,' se encontra na posicao ', POS)
senão escrever (DADO,' nao se encontra na tabela')
fim se
fim programa

INEFICIENTE:
INEFICIENTE O processo de busca continua mesmo
depois que o elemento foiencontrado

12

ACHOU ←falso
para I de 1 até N faça
se TAB[I] = DADO
então
ACHOU ← verdadeiro
POS ← I

Pesquisa Seqüencial

fim-se
fim para
se ACHOU
então escrever (DADO,' se encontra na posicao ', POS)
senão escrever (DADO,' nao se encontra na tabela')
fim se
fim programa

INEFICIENTE:
INEFICIENTE O processo de busca continua mesmo
depois que o elemento for encontrado
Parar oprocesso de
busca quando o dado
for encontrado
13

ACHOU ←falso
I←1
enquanto (ACHOU = falso) e (I≤N) faça
se DADO = TAB[I]
então
ACHOU ← verdadeiro
POS ← I

Pesquisa Seqüencial

senão I ← I + 1
fim se
fim enquanto
se ACHOU
então escrever (DADO,' se encontra na posicao ', POS)
senão escrever (DADO,' nao se encontra na tabela')
fim se
fim programa

Pesquisa Seqüencial com usoda variável lógica

14

I←1
POS ← 0
Pesquisa
enquanto (I ≤ N) e (POS = 0) faça
se DADO = TAB[I]
então POS ←I
fim-se
I ←I +1
fim enquanto
se POS ≠0
então escrever (DADO,' se encontra na posicao ', POS)
senão escrever (O elemento nao pertence ao conjunto)
fim-se
fim programa

Seqüencial

Pesquisa Seqüencial sem uso da variável lógica

15

Pesquisa Seqüencial com...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • dddd
  • dddd
  • Dddd
  • dddd
  • Dddd
  • Dddd
  • dddd
  • dddd

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!