Busca Binária, apresentação

Grupo:
Felipe Mateus
João Batista
Laiton Garcia

Definição: Encontrar em uma estrutura uma ou mais ocorrências de registros de dados com chaves iguais a uma chave de pesquisa.
Existem muitos métodos de pesquisa(sequencial, sequencial indexada, binária, interpolação, árvores, Hashing) cuja eficiência varia conforme:
1.Quantidade dos dados envolvidos
2.Frequência de inserções e retiradas de dados
3. Problema associado: ordenação de registros
4.Estruturas pré-ordenadas podem auxiliar no processo de pesquisa

• A busca sequencial é a forma mais simples de busca.

• É aplicável a uma tabela organizada como um vetor ou como uma lista encadeada,
• Percorre-se registro por registro em busca da chave
• Método para vetores e listas encadeadas
• Método mais simples
• Independe da estrutura estar pré-ordenada
• Melhor solução para pequenas quantidades de dados • No melhor caso executa 1 comparação e no pior caso n comparações

1. Depende da estrutura estar pré-ordenada
2. Boa solução para dados estáveis

Análise
• A cada iteração do algoritmo, o vetor é dividido ao meio. • A pesquisa binária não é recomendada para ser usada em aplicações muito dinâmicas.

Vantagens
Desempenho

Simplicidade da Implementação
Eficiência

Desvantagens
Nem todo arranjo está ordenado

Exige o uso de um arranjo para armazenar os dados

Vejamos um exemplo:
Se n=1000, o algoritmo de pesquisa sequencial irá executar 1000 comparações no pior caso. Por sua vez, o algoritmo de pesquisa binária irá executar 10 comparações no pior caso. Isso porque estamos sempre dividindo o intervalo ao meio:
1000, 500, 250, 125, 63, 32, 16, 8, 4, 2, 1

E se n=1.000.000.000 (1 bilhão) ?
* Pesquisa binária faz 30 comparações.
* Pesquisa sequencial faz 1.000.000.000 comparações!

EX: BUSCA
BINÁRIA
Recursiva

Interativa

Vetor

Índice
Conteúdo
Valor pesquisado 70

Inicio

0
4
6

Fim

Meio

7
(0+7)/2 =3,5
7
(4+7)/2 = 5
7