CadernoEm broto: já tem corpo. Vira Perene com mais texto e com o tempo sendo cuidado. O Zukan calcula sozinho; não é preciso fazer nada.
Busca binária, do jogo de adivinhar às entrevistas
· 2.499 palavras
Este caderno vai da brincadeira de adivinhar um número até as variações que caem em entrevista. Ele foi feito para mexer: tem uma lista para percorrer passo a passo, código que roda aqui mesmo, um treino com números sorteados e fichas que voltam para revisão.
1. A ideia: o jogo de adivinhar
Pense num número de 1 a 100. Eu chuto 50 e você só responde "maior" ou "menor". Se a resposta for "maior", eu acabei de descartar cinquenta números com uma pergunta. O próximo chute é 75, e descarto mais vinte e cinco. Em no máximo sete perguntas eu chego ao seu número, qualquer que seja.
A busca binária é esse jogo. O que a faz funcionar é uma condição só: a lista precisa estar ordenada. É a ordem que permite concluir, olhando um único item, que metade inteira da lista não interessa.
Antes de ler o código, percorra a lista abaixo. Escolha um número no controle, e antes de cada clique tente dizer onde o meio vai cair e qual metade será descartada.
Repare em duas coisas enquanto percorre. A primeira é que o intervalo só encolhe, nunca cresce. A segunda é que procurar um número que não existe, como 40, custa quase o mesmo que procurar um que existe: a busca só para quando o intervalo fica vazio.
2. O algoritmo
São três variáveis e uma pergunta repetida. inicio e fim marcam o trecho da lista que ainda pode conter o alvo. A cada volta, olhamos o item do meio e encolhemos o trecho.
O código abaixo roda aqui. Aperte Executar, depois troque o alvo e a lista e rode de novo.
3. Por que é tão rápida
Cada comparação corta o problema pela metade. A pergunta "quantos passos?" vira "quantas vezes dá para dividir n por 2 até sobrar um item?". A resposta é o logaritmo de n na base 2.
comparac¸o˜es no pior caso=⌊log2n⌋+1
O gráfico usa escala logarítmica no eixo vertical, senão a linha da busca binária ficaria colada no chão.
O que mais surpreende é o outro lado da conta: dobrar o tamanho da lista custa uma comparação a mais. De um milhão para dois milhões de itens, a busca linear ganha um milhão de passos e a binária ganha um.
Treine a conta até ela sair sem esforço. Os números são sorteados, e os que você errar voltam mais vezes.
4. Os três erros clássicos
A busca binária tem fama de ser o algoritmo simples que quase ninguém acerta de primeira. Os erros são sempre os mesmos, e todos moram nas bordas.
Erro 1: o laço que não acaba. Quem escreve inicio = meio em vez de inicio = meio + 1 cria um laço infinito. Com inicio = 4 e fim = 5, o meio é 4. Se o alvo estiver à direita, inicio continua 4 para sempre. A regra é: o meio já foi examinado, então ele sempre sai do intervalo.
Erro 2: esquecer o último item. Com while (inicio < fim) e fim inclusivo, a busca para quando sobra um item, sem olhar para ele. A lista [5] procurando 5 devolve -1. A condição e o significado de fim precisam combinar: fim inclusivo pede <=.
Erro 3: a soma que estoura. Em linguagens com inteiros de tamanho fixo, como Java e C, (inicio + fim) / 2 estoura quando a soma passa do maior inteiro. Esse erro ficou anos escondido em bibliotecas usadas no mundo todo, porque só aparece em listas com mais de um bilhão de itens. A forma segura é inicio + (fim - inicio) / 2, que dá o mesmo resultado sem somar dois números grandes.
Pergunta
Teste: o que este código devolve para a lista [2, 4, 6] procurando 6, se o laço for while (inicio < fim)?
Devolve -1. Primeira volta: início 0, fim 2, meio 1, valor 4, menor que 6, início vira 2. Agora início e fim são 2, a condição 2 < 2 é falsa e o laço termina sem examinar o índice 2, onde o 6 está.
5. As variações que caem em entrevista
Quase nenhuma entrevista pede a busca binária pura. Pedem uma destas três.
A primeira ocorrência
Na lista [1, 3, 3, 3, 7], a busca comum pode devolver qualquer um dos três. Para achar o primeiro 3, a mudança é não parar ao encontrar: guarda-se o candidato e a busca continua para a esquerda.
O ponto de inserção
"Em que posição este valor entraria para a lista continuar ordenada?" É a mesma busca, devolvendo inicio no fim em vez de -1. Quando o laço termina, inicio aponta para o primeiro item maior ou igual ao alvo. É isso que bisect_left faz em Python e lower_bound em C++.
A busca na resposta
A variação mais poderosa não procura numa lista. Procura num intervalo de respostas possíveis. Vale sempre que a pergunta tem esta forma: "qual é o menor valor que funciona?", e se um valor funciona, todos os maiores também funcionam.
Um exemplo: um navio precisa entregar pacotes em 5 dias, na ordem em que estão. Qual é a menor capacidade que dá conta? Capacidade 1.000 funciona, capacidade 1 não. Entre uma e outra existe um ponto de virada, e achar um ponto de virada é exatamente o que a busca binária faz. Testa-se a capacidade do meio: se dá tempo, a resposta está nela ou abaixo; se não dá, está acima.
Pergunta
Como saber se um problema aceita busca na resposta?
Procure a monotonia. Se "funciona com X" garante "funciona com X + 1", as respostas formam uma fila de não, não, não, sim, sim, sim, e a busca binária acha a virada. Se a resposta pula entre sim e não sem padrão, não serve.
6. Quando não usar
A lista não está ordenada e a busca é única. Ordenar custa mais do que procurar uma vez em linha reta.
A lista é minúscula. Com dez itens, as duas buscas terminam antes de você piscar, e a linear é mais difícil de errar.
Os dados mudam o tempo todo. Manter um vetor ordenado a cada inserção sai caro. Uma árvore balanceada ou uma tabela de dispersão costuma servir melhor.
Só se pergunta "existe ou não?". Um conjunto com tabela de dispersão responde em tempo constante, sem precisar de ordem.
7. Para fechar
Três frases resumem o caderno. A lista precisa estar ordenada. O meio sempre sai do intervalo. A condição do laço precisa combinar com o significado do fim.
Se você só for guardar uma coisa, guarde o hábito de testar com três listas antes de confiar no código: a vazia, a de um item e a de dois itens. Quase todo erro de borda aparece numa delas.
Reescrever a busca com fim exclusivo (fim = lista.length) e ver o que muda na condição e nas atualizações
Resolver "raiz quadrada inteira de n" com busca na resposta
Achar o ponto de rotação de uma lista ordenada que foi girada, como [30, 37, 41, 3, 8, 12]
Para quem está aprendendo algoritmos, vai fazer entrevista técnica ou usa busca binária há anos sem nunca ter entendido por que ela erra tanto na hora de escrever. Só precisa saber ler um laço em qualquer linguagem.
Busca binária acha um item numa lista ordenada jogando fora metade do que sobra a cada pergunta. Um milhão de itens pedem 20 perguntas. A ideia cabe numa frase; o difícil é acertar as bordas.
Preparando o objeto…
Interativo
title "Busca binária passo a passo"control alvo =371..99
A busca binária linha a linha
js
functionbuscaBinaria(lista, alvo) {let inicio =0;let fim =lista.length-1;while (inicio <= fim) {constmeio=Math.floor((inicio + fim) /2);if (lista[meio] === alvo) return meio;if (lista[meio] < alvo) inicio = meio +1;else fim = meio -1; }return-1;}constlista= [3,8,12,17,21,26,30,37,41,48];console.log("37 está no índice",buscaBinaria(lista,37));console.log("40 está no índice",buscaBinaria(lista,40));
Qual é o intervalo no começo?
Passo 1
A lista inteira, do índice 0 ao último. Aqui o fim é inclusivo: ele aponta para um item que ainda pode ser o alvo.
Não pode faltarinclusivolista inteira
Onde olhar?
Passo 2
No item do meio do intervalo que sobrou, arredondando para baixo.
O meio é menor que o alvo. E agora?
Passo 3
O alvo só pode estar à direita. O próprio meio já foi examinado, então o início pula para depois dele.
Erro comumif (lista[meio] < alvo) inicio = meio;
O meio é maior que o alvo. E agora?
Passo 4
O alvo só pode estar à esquerda, e o fim recua para antes do meio.
parecida com
Quando a busca desiste?
Passo 5
Quando o intervalo fica vazio, isto é, quando o início passa do fim.
Erro comumwhile (inicio < fim) {
O que o -1 quer dizer?
Que o alvo não está na lista. É uma convenção: nenhum índice válido é negativo.
Ver código
Preparando o objeto…
Onde a busca binária quebra
Tabela
Erro
Como aparece
Conserto
Laço infinito
inicio = meio
inicio = meio + 1
Último item ignorado
while (inicio < fim) com fim inclusivo
while (inicio <= fim)
Estouro de inteiro
(inicio + fim) / 2
inicio + (fim - inicio) / 2
Lista fora de ordem
Resposta errada, sem erro nenhum
Ordenar antes, ou não usar
Por que o meio precisa sair do intervalo?
Porque ele já foi comparado. Se continuar dentro, um intervalo de dois itens pode nunca encolher.
Não pode faltarjá comparadodois itens
Que lista mostra esse erro mais depressa?
Uma lista de um item só, procurando esse item: a busca devolve -1 sem ter olhado para ele.
Por que essa forma não estoura?
Porque fim - inicio nunca passa do tamanho da lista, e somar metade disso ao início não passa de fim.
Erro comum(inicio + fim) / 2
O que acontece numa lista bagunçada?
A busca devolve -1 ou um índice errado e segue em frente, sem avisar. É o erro mais perigoso dos quatro.
parecida com
Ver código
Quanto custa procurar
Tabela
Itens na lista
Busca linear (pior caso)
Busca binária (pior caso)
100
100
7
1.000
1.000
10
1.000.000
1.000.000
20
1.000.000.000
1.000.000.000
30
Quando a busca linear ainda é a escolha certa?
Quando a lista não está ordenada, quando é tão pequena que tanto faz, ou quando a busca acontece uma vez só e ordenar custaria mais.
Não pode faltarordenadapequenauma vez
Um milhão de itens: quantas comparações?
No máximo 20, porque 2 elevado a 20 passa de um milhão.
Lacuna20
De um milhão para um bilhão, quanto piora?
Só dez comparações a mais. Multiplicar a lista por mil soma dez passos, porque 2 elevado a 10 é 1.024.
Não pode faltardezmultiplicarsomar
Fórmula
⌊log2n⌋+1
Como calcular o pior caso?
É quantas vezes a lista pode ser cortada ao meio, mais um.
Caso Uma lista ordenada tem {n} itens. No pior caso, quantas comparações a busca binária faz?
if (fim !== inicio) f.text(fim +0.5,2.3,"fim", { anchor:"middle" });
}
if (meio !==undefined) f.text(meio +0.5,2.7,"meio", { anchor:"middle", strong:true });
}
functionrecomecar() {
alvo =Math.round(setting("alvo",37));
inicio =0;
fim =lista.length-1;
passos =0;
achou =false;
desenhar();
nota.textContent ="Procurando "+ alvo +" em "+lista.length+" itens. O intervalo é a lista inteira.";
}
functionpasso() {
if (achou || inicio > fim) return;
constmeio=Math.floor((inicio + fim) /2);
passos +=1;
constvalor= lista[meio];
if (valor === alvo) {
achou =true;
desenhar(meio);
nota.textContent ="Passo "+ passos +": lista["+ meio +"] é "+ valor +". Achou, em "+ passos +" comparação(ões).";
return;
}
if (valor < alvo) {
desenhar(meio);
inicio = meio +1;
nota.textContent ="Passo "+ passos +": lista["+ meio +"] é "+ valor +", menor que "+ alvo +". Tudo até o índice "+ meio +" sai. Novo início: "+ inicio +".";
} else {
desenhar(meio);
fim = meio -1;
nota.textContent ="Passo "+ passos +": lista["+ meio +"] é "+ valor +", maior que "+ alvo +". Tudo a partir do índice "+ meio +" sai. Novo fim: "+ fim +".";
}
if (inicio > fim) nota.textContent +=" O intervalo ficou vazio: "+ alvo +" não está na lista ("+ passos +" comparações).";
title A primeira ocorrênciaarea Algoritmosobject code js @primeira function primeiraOcorrencia(lista, alvo) { let inicio = 0; let fim = lista.length - 1; let resposta = -1; while (inicio <= fim) { const meio = inicio + Math.floor((fim - inicio) / 2); if (lista[meio] >= alvo) { if (lista[meio] === alvo) resposta = meio; fim = meio - 1; } else { inicio = meio + 1;
Mermaid
flowchartTD A[inicio = 0, fim = último índice]--> B{inicio <= fim?} B -- não --> F[não está na lista] B -- sim --> C[meio = metade do intervalo] C --> D{lista no meio é o alvo?} D -- sim --> E[devolve meio] D -- menor que o alvo --> G[inicio = meio + 1] D -- maior que o alvo --> H[fim = meio - 1] G --> B H --> B
Quadro
title A busca binária linha a linhaarea Algoritmosobject code js @busca function buscaBinaria(lista, alvo) { let inicio = 0; let fim = lista.length - 1; while (inicio <= fim) { const meio = Math.floor((inicio + fim) / 2); if (lista[meio] === alvo) return meio; if (lista[meio] < alvo) inicio = meio + 1; else fim = meio - 1; } return -1; } const lista = [3, 8, 12, 17, 21, 26, 30, 37, 41, 48]; console.log("37 está no índice", buscaBinaria(lista, 37)); console.log("40 está no índice", buscaBinaria(lista, 40));step 1 @busca "let fim = lista.length - 1;" Qual é o intervalo no começo? ^intervalo A lista inteira, do índice 0 ao último. Aqui o fim é inclusivo: ele aponta para um item que ainda pode ser o alvo.keywords inclusivo, lista inteirastep 2 @busca "const meio = Math.floor((inicio + fim) / 2);" Onde olhar? ^meio No item do meio do intervalo que sobrou, arredondando para baixo.step 3 @busca "if (lista[meio] < alvo) inicio = meio + 1;" O meio é menor que o alvo. E agora? ^descarta O alvo só pode estar à direita. O próprio meio já foi examinado, então o início pula para depois dele.wrong"if (lista[meio] < alvo) inicio = meio;"step 4 @busca "else fim = meio - 1;" O meio é maior que o alvo. E agora? ^descarta-dir O alvo só pode estar à esquerda, e o fim recua para antes do meio.not^descartastep 5 @busca "while (inicio <= fim) {" Quando a busca desiste? ^para Quando o intervalo fica vazio, isto é, quando o início passa do fim.wrong"while (inicio < fim) {"pin @busca "return -1;" O que o -1 quer dizer? ^nao-achou Que o alvo não está na lista. É uma convenção: nenhum índice válido é negativo.
title "Quantas comparações"control cartoes =63..12"Cartões por rodada"---import { practice, draw, setting } from"zukan";consttamanhos= [7,8,15,16,31,32,100,255,256,1000,1024,5000,65536,1000000];practice({ title:"Quantas comparações", rounds:setting("cartoes",6),card(c) {constn=draw(tamanhos, { key: (v) =>"n="+ v });constresposta=Math.floor(Math.log2(n)) +1;c.text("Uma lista ordenada tem "+n.toLocaleString("pt-BR") +" itens. No pior caso, quantas comparações a busca binária faz?");c.typed(resposta, { item:"n="+ n, expected:String(resposta), why:"2 elevado a "+ (resposta -1) +" é "+ (2** (resposta -1)).toLocaleString("pt-BR") +", que cabe em "+n.toLocaleString("pt-BR") +". Então são " }); },});
Quadro
title Onde a busca binária quebraarea Algoritmosobject table @erros | Erro | Como aparece | Conserto | | Laço infinito | inicio = meio | inicio = meio + 1 | | Último item ignorado | while (inicio < fim) com fim inclusivo | while (inicio <= fim) | | Estouro de inteiro | (inicio + fim) / 2 | inicio + (fim - inicio) / 2 | | Lista fora de ordem | Resposta errada, sem erro nenhum | Ordenar antes, ou não usar |pin @erros C2 Por que o meio precisa sair do intervalo? ^sai-meio Porque ele já foi comparado. Se continuar dentro, um intervalo de dois itens pode nunca encolher.keywords já comparado, dois itenspin @erros B3 Que lista mostra esse erro mais depressa? ^um-item Uma lista de um item só, procurando esse item: a busca devolve -1 sem ter olhado para ele.pin @erros C4 Por que essa forma não estoura? ^estouro Porque fim - inicio nunca passa do tamanho da lista, e somar metade disso ao início não passa de fim.wrong"(inicio + fim) / 2"pin @erros B5 O que acontece numa lista bagunçada? ^bagunca A busca devolve -1 ou um índice errado e segue em frente, sem avisar. É o erro mais perigoso dos quatro.not^um-item
Quadro
title Quanto custa procurararea Algoritmosobject table @custo | Itens na lista | Busca linear (pior caso) | Busca binária (pior caso) | | 100 | 100 | 7 | | 1.000 | 1.000 | 10 | | 1.000.000 | 1.000.000 | 20 | | 1.000.000.000 | 1.000.000.000 | 30 |object formula @passos \lfloor \log_2 n \rfloor + 1pin @custo C4 Um milhão de itens: quantas comparações? ^milhao No máximo 20, porque 2 elevado a 20 passa de um milhão.gap"20"pin @custo C5 De um milhão para um bilhão, quanto piora? ^bilhao Só dez comparações a mais. Multiplicar a lista por mil soma dez passos, porque 2 elevado a 10 é 1.024.keywords dez, multiplicar, somarpin @passos Como calcular o pior caso? ^pior-caso É quantas vezes a lista pode ser cortada ao meio, mais um.case Uma lista ordenada tem {n} itens. No pior caso, quantas comparações a busca binária faz? n = 1000..1000000answer floor(log2(n)) + 1pin @custo B2 Quando a busca linear ainda é a escolha certa? ^linear Quando a lista não está ordenada, quando é tão pequena que tanto faz, ou quando a busca acontece uma vez só e ordenar custaria mais.keywords ordenada, pequena, uma vez