aula_listasOrdenadas

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Listas Ordenadas
Estrutura de Dados I
Profª Valéria de Carvalho Santos
Universidade Estadual Paulista “Júlio de Mesquita”
Listas ordenadas
Operações em representação estática
• Características:
• Lista mantida em ordem crescente/decrescente 
segundo o valor da chave
• Ordem facilita a pesquisa
• Ordem dificulta inserção
Operações (ordenada)
Operações em representação estática
• Inserir item
Operações (ordenada)
Operações em representação estática
• Buscar item (dada uma chave)
Operações (ordenada)
Operações em representação estática
• Buscar item (dada uma chave): Busca binaria
• Dividir e conquistar
• Segmentar a lista em duas partes
• Determinar em que parte a chave buscada se 
encontra
• Concentrar a busca no segmento correto
Operações (ordenada)
Operações em representação estática
• Buscar item (dada uma chave): Busca binaria
Exercícios
• Implemente busca binária de forma recursiva.
• Modifique busca para achar todas as ocorrências de 
uma chave.