Verificando Um por Tempo
Pesquisa Linear: Verifique Todos
Imaginar que você tem 10 cartões virados para baixo, numerados de 1 a 10, embaralhados em um arranjo aleatório.
Você quer encontrar o cartão com o número 7.
Você vira cartões uma por vez, da esquerda para a direita, até encontrar.
| Cenário | Voltas necessárias |
|----------|-------------|
| Melhor caso | 1 volta (sorte, primeiro tentativa!) |
| Pior caso | 10 voltas (era o último cartão) |
| Média | cerca de 5 voltas |
Agora imagine 100 cartões. Média: cerca de 50 voltas.
1.000 cartões? Média: cerca de 500 voltas.
Vê o padrão? Duplique os cartões, duplique o trabalho. O trabalho cresce em uma linha reta.
Os cientistas da computação chamam isso de pesquisa linear - linear significa que o trabalho cresce como uma linha: constante e previsível.
A pesquisa linear funciona em qualquer lista, organizada ou não. Isso faz com que seja simples. Mas pode ficar lento.
Quantos Nomes?
Você tem uma lista de classe de 20 nomes escritos em um arranjo aleatório.
Você precisa encontrar o nome Zoe.
Você verifica os nomes uma por vez, do topo da lista para baixo.
Corte a Lista ao Meio
Busca Binária: Pule para o Meio
A busca binária tem uma regra: a lista deve estar ordenada primeiro.
Se sua lista de 20 nomes for de A a Z, você pode usar a busca binária.
Como funciona: abra para o nome do meio (nome #10). Pergunte: a Zoe está antes ou depois deste nome?
O Z está perto do final do alfabeto, então a Zoe está DEPOIS do meio. Jogue fora a primeira metade. Agora você tem apenas nomes de 11 a 20.
Verifique o meio desses 10 nomes (nome #15). O Z está depois do M, então a Zoe está depois do nome #15. Jogue fora os nomes de 11 a 14. Agora você tem nomes de 16 a 20.
Continue cortando em pedaços iguais. Cada verificação remove metade dos nomes restantes.
Tamanho da lista | Verificações máximas com busca binária |
|-----------|-------------------------------|
| 20 nomes | no máximo 5 verificações |
| 1.000 nomes | no máximo 10 verificações |
| 1.000.000 nomes | no máximo 20 verificações |
Compare com a busca linear em 1.000.000 de nomes: uma média de 500.000 verificações.
A busca binária corta a lista ao meio a cada vez. Cortar ao meio repetidamente chega a 1 muito rapidamente - isso é por que ela fica tão rápida.
Encontre 'fig' em uma Lista Ordenada
Aqui está uma lista ordenada de 8 palavras:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Você quer encontrar fig usando a busca binária.
Lembrete: verifique o meio, pergunte se seu alvo está antes ou depois, e depois corte a lista ao meio.
Troca de Vizinhança em Ordem
Bubble Sort: Compare Vizinhos & Troca
O bubble sort organiza uma lista comparando dois itens adjacentes uma vez.
Se dois vizinhos estiverem desordenados — troque-os.
Faça várias passadas pela lista até não haver mais trocas necessárias.
Exemplo: ordene [5, 3, 8, 1]
Passada 1:
- Compare 5 & 3. 5 > 3, então troque → [3, 5, 8, 1]
- Compare 5 & 8. 5 < 8, sem troca → [3, 5, 8, 1]
- Compare 8 & 1. 8 > 1, então troque → [3, 5, 1, 8]
Passada 2:
- Compare 3 & 5. OK → [3, 5, 1, 8]
- Compare 5 & 1. 5 > 1, troque → [3, 1, 5, 8]
- Compare 5 & 8. OK → [3, 1, 5, 8]
Passada 3:
- Compare 3 & 1. 3 > 1, troque → [1, 3, 5, 8]
- Compare 3 & 5. OK. Compare 5 & 8. OK.
Feito! [1, 3, 5, 8] ✓
Observação: o maior número submerge para o fim da lista em cada passada. Esse é o motivo pelo qual o bubble sort recebeu seu nome.
O bubble sort funciona. Ele não é o mais rápido para listas grandes, mas é fácil de entender — perfeito para aprender.
Ordene [4, 2, 7, 1] com Bubble Sort
Ordene esta lista usando bubble sort: [4, 2, 7, 1]
Mostre a lista após cada passada. Conte quantas passadas foram feitas para terminar.