DS & II

Capítulo 19 - Algoritmos de Busca

Leitura de 4 min

🚀 Capítulo 19: Algoritmos de Busca (Linear e Binária) (Tema: Onde está o Wally?)

NOTE

Este capítulo utiliza a temática de Onde está o Wally? para explicar os algoritmos de busca. Encontrar alguém na multidão exige estratégia!

1. 🎯 Objetivo da Aula

Compreender a diferença entre a Busca Linear e a Busca Binária, entendendo a importância de ter os dados ordenados para alcançar a máxima eficiência .

2. 🏢 O Cenário Prático (Seu Desafio)

Você tem um livro do “Onde está o Wally?“.

  • Cenário A: As pessoas na página estão todas misturadas. Você precisa olhar pessoa por pessoa, da esquerda para a direita, até achar o Wally. Isso é a Busca Linear.
  • Cenário B: Imagine que, por mágica, as pessoas na página estivessem organizadas por altura, da menor para a maior! Para achar o Wally (que tem uma altura média), você não precisa olhar um por um. Você olha a pessoa que está exatamente no meio da página. Se ela for mais alta que o Wally, você já sabe que o Wally está na metade esquerda! Você acabou de eliminar metade da página com um único olhar. Isso é a Busca Binária.

Seu desafio é entender a velocidade incrível da Busca Binária!

3. 🧠 Fundamentos: A Teoria Traduzida

🔍 1. Busca Linear

  • Como funciona: Percorre a estrutura do início ao fim, comparando cada elemento com o valor buscado.
  • Requisito: Nenhum. Funciona em listas bagunçadas.
  • Eficiência: (Se a lista tiver 1 milhão de pessoas, no pior caso você faz 1 milhão de buscas).

🎯 2. Busca Binária

  • Como funciona: Divide a lista ao meio repetidamente. Compara o item do meio com o valor buscado e descarta a metade onde o item com certeza não está.
  • Requisito: A lista PRECISA estar ordenada!
  • Eficiência: (Se a lista tiver 1 milhão de pessoas, no pior caso você faz apenas cerca de 20 buscas!).

4. 📖 Exemplo Guiado: Adivinhando o Número

Pense em um jogo de adivinhar um número de 1 a 100.

  • Se você chutar 1, depois 2, depois 3… você está fazendo Busca Linear.
  • Se você chutar 50 e eu disser “É maior”, você agora só precisa procurar de 51 a 100. Você eliminou 50 números com um chute! Isso é Busca Binária.

5. 🛠️ Prática Obrigatória 1: O Número de Chutes

Se estivermos jogando o jogo de adivinhar o número de 1 a 100 usando a Busca Binária:

  1. Qual é o seu primeiro chute?
  2. Se a resposta for “É menor”, qual é o seu segundo chute?
  3. Qual é o número máximo de chutes que você precisará dar para acertar qualquer número de 1 a 100?

6. 🛠️ Prática Obrigatória 2: Vale a pena ordenar?

A Busca Binária é muito mais rápida, mas exige que a lista esteja ordenada. Se você tem uma lista bagunçada e só vai fazer uma única busca nela, vale a pena gastar tempo ordenando a lista (com Quick Sort) só para poder usar a Busca Binária? Ou é melhor fazer uma Busca Linear direto?

7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)

  1. Faça o Commit: No GitHub Desktop, digite a mensagem (ex: Finaliza Capítulo 19 Estruturas de Dados) e clique em Commit to main.
  2. Envie para a Nuvem (Push): Clique em Push origin.

8. 📂 Estrutura de Pastas

mod_09_estruturas_de_dados/
├── capitulos/
│   ├── capitulo_19_busca.md
│   └── codigos/
│       └── cap19/
│           └── busca_binaria.js

9. 💡 Checkpoint de Lógica

Por que o algoritmo de Busca Binária não funciona em uma Lista Ligada (Linked List), mesmo que ela esteja ordenada? (Dica: Lembra como acessamos o elemento do meio em uma lista ligada?).

10. 🔥 Desafio de Fixação

Pesquise o que é a Busca por Interpolação (Interpolation Search) e como ela tenta ser ainda mais inteligente que a Busca Binária (parecido com o modo como nós procuramos uma palavra no dicionário de papel).

🔑 Gabarito de Código/Fórmulas

Gabarito da Prática 1:

  1. Primeiro chute: 50 (o meio).
  2. Segundo chute: 25 (o meio entre 1 e 49).
  3. Número máximo de chutes: 7 (pois , que é maior que 100).

← Capitulo Anterior | Proximo Capitulo →

Visão de gráfico

Backlinks