Busca Binária Clássica sem Bugs
Domine o loop com low, high e mid.
Busca Binária Clássica sem Bugs é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Reduza o espaço de busca pela metade
A busca binária encontra um valor em uma lista ordenada reduzindo o intervalo pela metade a cada passo. Isso transforma uma varredura lenta O(n) em uma busca rápida O(log n).
a = [1, 3, 5, 7, 9] # must be sortedEstar ordenado é a única regra
A busca binária só funciona com dados ordenados. Se a lista não estiver ordenada, ordene-a primeiro; caso contrário, o resultado não terá sentido e estará errado.
a.sort() # ascending order requiredDois limites
Comece com dois ponteiros: low no índice 0 e high no último índice. Se estiver presente, o alvo sempre estará entre eles.
low, high = 0, len(a) - 1Encontre o meio com segurança
Calcule mid como low + (high - low) // 2. Em Python, o estouro não é um problema, mas essa forma é o hábito seguro em qualquer lugar.
mid = low + (high - low) // 2Três resultados
Compare a[mid] com o alvo. Ou você o encontrou, ou ele é pequeno demais, ou é grande demais. Cada caso reduz o intervalo de uma forma diferente.
if a[mid] == target:
return midPequeno demais, vá para a direita
Se a[mid] for menor que o alvo, a resposta deve estar à direita. Mova low para mid + 1 e descarte a metade esquerda.
elif a[mid] < target:
low = mid + 1Grande demais, vá para a esquerda
Se a[mid] for maior que o alvo, procure na metade esquerda. Mova high para mid - 1 para nunca verificar mid novamente.
else:
high = mid - 1A condição do laço
Continue enquanto low for menor ou igual a high. Quando eles se cruzarem, o intervalo estará vazio e o alvo não estará presente.
while low <= high:
mid = low + (high - low) // 2Informe quando não encontrar
Se o laço terminar sem encontrar uma correspondência, o valor estará ausente. Retorne -1 por convenção, para que quem chamar a função possa distinguir sucesso de falha.
return -1 # target not in listA armadilha do deslocamento de um
O erro clássico é esquecer o +1 ou -1 ao mover um ponteiro. Se você o esquecer, mid será testado novamente para sempre, causando um laço infinito.
low = mid + 1 # not low = midUse a biblioteca quando puder
Para um teste simples de pertencimento, o módulo bisect do Python já oferece uma busca sem erros. Escreva o laço manualmente apenas quando precisar de uma lógica personalizada.
import bisect
i = bisect.bisect_left(a, target)Verificação rápida
Pense no que mantém o laço correto.
Recapitulação: busque sem erros
Agora você pode definir low e high, calcular mid com segurança, reduzir o lado correto e evitar a armadilha do deslocamento de um. A busca logarítmica está ao seu alcance. 🎯
Perguntas Frequentes
A aula “Busca Binária Clássica sem Bugs” é grátis?
Sim — o texto completo de “Busca Binária Clássica sem Bugs” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Busca Binária Clássica sem Bugs”?
Domine o loop com low, high e mid. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.
Quanto tempo leva a aula “Busca Binária Clássica sem Bugs”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Busca Binária Clássica sem Bugs
- bisect_left e bisect_right
- Primeiro True: Busca Binária por Predicado
- Busca Binária na Resposta