Disciplinas UFC

Estruturas de Dados

aula 04:  A busca binária   (pdf, video)

< Figura >
  1. A ideia mais importante de todas
plano da aula  

1.  Introdução
  1. tempo O(n) é uma porcaria ...

2.  A busca pula-pula   
  1. Será que uma busca precisa levar tempo O(n) ?
    ◦  análise:  O ( n )

3.  Acelerando a busca pula-pula  
  1. aumentando o pulo, a medida que a gente pula
    ◦  análise:  O ( log 2 n)

4.  A busca binária  
  1. diminuindo o pulo, a medida que a gente pula
    ◦  análise:  O (log n)

5.  O algoritmo Mergesort  
  1. outra aplicação da técnica da divisão
lista de exercícios 04   (pdf)
exercício 1:   A busca ternária
< Figura >
exercício 2:   Desacelerando a busca acelerada
< Figura >
exercício 3:   Buscando vários elementos
< Figura >
exercício 4:   Busca em duas listas
< Figura >
exercício 5:   Busca na matriz
< Figura >


↩︎ Voltar