Busca Binária
Introduzido| English | Significado |
|---|---|
| sorted/ˈsɔːtɪd/ | ordenado |
| Binary search/ˈbaɪnəri sɜːtʃ/ | busca binária |
| target/ˈtɑːɡɪt/ | alvo |
| middle/ˈmɪdl/ | meio |
| halves/hɑːvz/ | metades |
| comparison/kəmˈpærɪsn/ | comparação |
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
Encontrando rápido em uma lista ordenada
- Busca binária é uma forma rápida de localizar um valor alvo em uma lista ordenada.
- "Sorted" significa que os valores estão em ordem — do menor para o maior, digamos.
- É muito mais rápida do que verificar cada item.
- Mas ela tem um requisito estrito.
A busca binária precisa de dados ordenados. Em uma lista não ordenada, ela pode pular o alvo e perdê-lo. Sempre ordene primeiro — ou use uma busca diferente.
A busca binária só pode ser usada em dados que estão:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Em dados desordenados ela pode não encontrar o alvo.
Verifique o meio, depois divida ao meio
- A ideia é simples: verifique o elemento central. Então:
- se o meio igualar o alvo, você o encontrou;
- se o alvo for menor, pesquise apenas a metade esquerda;
- se o alvo for maior, pesquise apenas a metade direita.

A busca binária reduz o intervalo a cada passo (a lista deve estar ordenada)
Busca linear vs busca binária
busca binária reduz o intervalo pela metade a cada passo
A busca linear verifica cada item; a busca binária divide uma lista ordenada pela metade a cada comparação, exigindo muito menos passos.
Se o alvo for maior que o elemento do meio, a próxima busca binária olha na:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Um alvo maior deve estar na metade direita (maior).
Cada comparação na busca binária ______ a parte restante da lista.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Dividir pela metade a cada passo é por que é tão rápida.
Aproximadamente quantas verificações de busca binária são necessárias para uma lista ordenada de 1000 itens? (2^10 = 1024)
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Porque 2^10 = 1024 ≥ 1000, cerca de 10 divisões bastam.
Por que é tão rápida
- Cada comparação reduz à metade a parte restante da lista.
- Para 1000 itens, uma busca linear pode precisar de até 1000 verificações.
- A busca binária precisa de no máximo cerca de 10, porque $2^{10} = 1024$.
- Quanto maior a lista, maior a vantagem.
A busca binária encontra 14 em [2,5,8,11,14,17,20] em quantas comparações?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Meio 11 → direita; meio 17 → esquerda; meio 14 → encontrado: 3 comparações.
Em uma grande lista ordenada, a busca linear requer menos comparações do que a busca binária.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Falso. A busca binária reduz a lista pela metade em cada etapa, exigindo muito menos comparações do que verificar cada item sequencialmente.
Versus busca linear
- Uma busca linear verifica cada elemento, um por um.
- A busca binária supera a busca linear em listas grandes ordenadas reduzindo à metade a cada etapa.
Pesquise [2, 5, 8, 11, 14, 17, 20] por 14. Meio é 11; 14 > 11 → pesquise a metade direita [14, 17, 20]. Meio é 17; 14 < 17 → pesquise [14]. Meio é 14 — encontrado em apenas 3 comparações. Uma busca linear levaria 5.
Busca binária encontra um alvo em uma lista ordenada verificando o meio e mantendo apenas a metade que poderia contê-lo. Cada comparação reduz à metade o intervalo, então 1000 itens precisam de ~10 verificações — muito menos que as 1000 de uma busca linear. Ela funciona apenas em dados ordenados.