Busca binária na prática: 1 milhão em milissegundos

Busca binária na prática resolve o problema de achar um item em uma lista ordenada de 1 milhão de registros em cerca de 20 comparações, com tempo de execução abaixo de 1 milissegundo em JavaScript. Veja o passo a passo, o código e a comparação com a busca linear.

Busca binária na prática: a resposta direta

Busca binária na prática encontra um elemento em uma lista ordenada descartando metade das posições a cada comparação, o que resulta em tempo logarítmico em vez de linear. Em uma lista ordenada de 1 milhão de itens, isso significa no máximo 20 comparações. A busca linear, no mesmo cenário, pode chegar a 1 milhão.

A ideia central é simples: você olha o elemento do meio, compara com o alvo e decide qual metade descartar. Como a lista está ordenada, essa decisão é segura. Se o meio é menor que o alvo, tudo à esquerda também é menor. Se é maior, tudo à direita é maior.

A condição indispensável é que a lista esteja ordenada. Sem isso, a lógica de descarte não funciona e o algoritmo não pode ser aplicado.

Em 2026, esse conceito continua sendo um dos fundamentos mais cobrados em entrevistas técnicas e um dos mais esquecidos por quem usa assistentes de código no dia a dia. A explicação canônica do algoritmo está no livro Entendendo Algoritmos, de Aditya Bhargava, um guia ilustrado que trata pesquisa binária, notação Big O, quicksort, tabelas hash e grafos com exemplos visuais.

O problema: encontrar um protocolo em 1 milhão de registros

O cenário é um sistema de atendimento com protocolos numéricos em ordem crescente, como 1001, 1008, 1012, 1019, 1024, 1030 e 1038. O objetivo é localizar a posição de um protocolo específico nessa fila. Com poucos itens, qualquer abordagem funciona. Com 1 milhão, a diferença entre os algoritmos se torna decisiva.

A busca linear percorre posição por posição até encontrar o alvo. Se o protocolo procurado estiver na última posição de uma lista de 1 milhão, são 1 milhão de comparações. A busca binária, no mesmo cenário, faz no máximo 20 comparações porque divide o espaço de busca pela metade a cada passo.

Em índices de lista, a contagem começa em zero. Uma lista com 100 elementos tem índices de 0 a 99. Em uma lista com 7 posições, o último índice é 6. Essa convenção importa para calcular corretamente o ponto médio e os limites do intervalo de busca.

Uma observação prática: a lista de protocolos pode estar ordenada em ordem crescente ou decrescente, e pode conter strings em ordem alfabética. A lógica de descarte só depende de existir uma ordem consistente entre os elementos.

Como a busca binária funciona passo a passo

Você mantém dois ponteiros, inicio e fim, que delimitam a região ainda candidata. A cada iteração, calcula o meio, compara o valor nessa posição com o alvo e ajusta um dos ponteiros. Veja a sequência com a lista de protocolos e o alvo 1024:

1. Lista completa: índices 0 a 6, valores 1001, 1008, 1012, 1019, 1024, 1030, 1038. Meio calculado em 3, valor 1019. Como 1019 é menor que 1024, o inicio passa para 4.

2. Região ativa: índices 4 a 6, valores 1024, 1030, 1038. Meio calculado em 5, valor 1030. Como 1030 é maior que 1024, o fim passa para 4.

3. Região ativa: índice 4, valor 1024. Meio calculado em 4, valor igual ao alvo. A posição retornada é 4.

Quando o alvo não existe na lista, os ponteiros se cruzam e inicio fica maior que fim. Nesse momento o algoritmo retorna -1, indicando que o protocolo não foi encontrado.

O mesmo raciocínio vale para qualquer alvo. Buscando o protocolo 1008: o meio é 1019, que é maior, então o fim vai para 2 e a região fica com 1001, 1008 e 1012. O novo meio é o índice 1, valor 1008, igual ao alvo. Buscando o 1012: o meio 1019 é maior, o fim vai para 2, o novo meio é o índice 1, valor 1008, que é menor, então o inicio vai para 2 e sobra só o 1012.

Um erro comum de quem implementa pela primeira vez é achar que o alvo pode ter sido descartado por engano. Ele não pode. Se a lista está ordenada, o valor do meio sempre separa os menores dos maiores, e o descarte é seguro por construção.

Por que a complexidade é O(log n) e não O(n)

A busca binária tem complexidade O(log n) porque divide o espaço de busca pela metade a cada comparação. O número máximo de etapas é log₂ de n, em que n é o tamanho da lista. Com 100 itens, o máximo é 7 etapas. Com 240.000 itens, o máximo é 18 etapas. Com 1 milhão, cerca de 20.

O logaritmo é sempre de base 2 aqui porque a divisão é sempre por dois. Logaritmo é a operação inversa da exponencial: log de 100 na base 10 é 2, porque 10² = 100.

A busca linear tem complexidade O(n) porque, no pior caso, percorre todos os elementos. O pior caso ocorre quando o alvo está na última posição ou não existe na lista. A diferença entre O(n) e O(log n) cresce rápido conforme n aumenta.

Medir tempo de execução com console.time e console.timeEnd em JavaScript serve para comparação pontual, mas não substitui a análise de complexidade. O tempo varia conforme a máquina, o clock da CPU, o número de núcleos de processamento e os processos em execução. A notação Big O descreve o crescimento do algoritmo de forma independente do hardware, e é por isso que ela funciona como medida universal.

Uma consequência prática dessa análise: a busca binária tem pior caso previsível. Você sabe de antemão o teto de 20 comparações para 1 milhão de itens. A busca linear não tem teto útil, porque depende da posição em que o alvo está. Para garantir um limite de latência em um sistema, isso muda tudo.

Comparação: busca binária contra busca linear

As duas abordagens resolvem o mesmo problema, mas com custos muito diferentes. A tabela abaixo resume as diferenças principais, considerando um alvo que pode estar em qualquer posição da lista:

Critério	Busca linear (força bruta)	Busca binária
Pré-requisito	Nenhum, aceita lista em qualquer ordem	Lista ordenada
Complexidade de tempo	O(n)	O(log n)
Comparações no pior caso (1 milhão de itens)	1.000.000	20
Comparações no pior caso (240.000 itens)	240.000	18
Pior caso previsível	Não	Sim
Melhor caso	1 comparação, se o alvo estiver no início	Cerca de 1 comparação, se o alvo estiver no meio
Uso de memória extra	Nenhum	Ponteiros inicio, fim e meio

A busca linear não depende de ordenação e aceita qualquer lista. A busca binária exige lista ordenada, mas oferece previsibilidade: você sabe de antemão o número máximo de comparações necessárias. Essa previsibilidade é útil quando o sistema precisa garantir um limite de latência.

Em medições feitas com listas geradas em JavaScript, a busca linear percorrendo 100 milhões de elementos até o último item levou dezenas de segundos, enquanto a busca binária no mesmo intervalo ficou abaixo de 1 milissegundo. Os valores absolutos dependem do ambiente, mas a ordem de grandeza da diferença se mantém.

Medições concretas do vídeo original, em uma lista de 1 milhão de elementos com o alvo na última posição: a força bruta levou 2,427 ms e a busca binária levou 0,049 ms, ambas encontrando a posição 999.999. Em 100 milhões de elementos com o alvo no fim, a busca linear levou 51 s, contra 0,032 ms da busca binária. O número varia a cada execução, mas o padrão se repete.

A comparação também expõe o ponto fraco da busca linear: o tempo dela depende da posição do alvo. Buscando um elemento na segunda posição da lista de 100 milhões, a força bruta responde quase instantaneamente, até mais rápido que a busca binária. Buscando na posição 50.000, já são 0,279 ms, enquanto a busca binária fica em 0,026 ms. Na posição 1.500.000, o tempo passa de 1 segundo. Por isso a busca linear é imprevisível, e a binária não.

Há uma restrição de ambiente que aparece quando a lista cresce: gerar 500 milhões ou 300 milhões de elementos em JavaScript estoura a memória do heap e derruba a execução. 100 milhões funcionam e já mostram a diferença. Em 1 bilhão de itens, o processo falha antes de qualquer medição.

Implementando busca binária em JavaScript

A implementação usa um laço while que continua enquanto inicio for menor ou igual a fim. Dentro do laço, o meio é calculado com Math.floor((inicio + fim) / 2) e comparado com o alvo.

• Se protocolos[meio] é igual ao alvo, retorne meio.

• Se protocolos[meio] é menor que o alvo, atualize inicio = meio + 1 para descartar a metade esquerda, incluindo o próprio meio.

• Se protocolos[meio] é maior que o alvo, atualize fim = meio - 1 para descartar a metade direita.

Se o laço terminar sem encontrar o alvo, retorne -1. Esse padrão funciona em qualquer linguagem que suporte arrays indexados e comparação de valores. A diferença entre linguagens fica na sintaxe, não na lógica.

function buscaBinaria(protocolos, alvo) {
  let inicio = 0;
  let fim = protocolos.length - 1;

  while (inicio <= fim) {
    const meio = Math.floor((inicio + fim) / 2);

    if (protocolos[meio] === alvo) return meio;
    if (protocolos[meio] < alvo) {
      inicio = meio + 1;
    } else {
      fim = meio - 1;
    }
  }

  return -1;
}

O Math.floor no cálculo do meio não é decorativo. Sem ele, uma soma de índices ímpares produziria um índice fracionário, e protocolos[4.5] é undefined. O floor garante que o índice aponte para uma posição real da lista.

Um detalhe de implementação que evita estouro em linguagens de tipagem fixa: (inicio + fim) / 2 pode ultrapassar o limite do inteiro quando os dois índices são grandes. A alternativa segura é inicio + Math.floor((fim - inicio) / 2), que chega ao mesmo valor sem somar dois índices altos. Em JavaScript os números são de ponto flutuante e o problema não aparece na prática, mas vale conhecer a variante.

Do outro lado, a busca linear é o laço simples que percorre o array do índice 0 até o último e retorna o índice quando encontra o alvo. Se terminar o laço sem achar, retorna -1. Com 7 protocolos, as duas versões retornam a mesma posição, e é justamente aí que o teste com uma lista pequena engana: só com uma lista grande a diferença fica visível.

Quando a lista não está ordenada: quicksort e dividir para conquistar

Se a lista está desordenada, a busca binária não pode ser aplicada diretamente. Uma alternativa é ordenar a lista primeiro e depois buscar. O quicksort é um dos algoritmos de ordenação que usa a estratégia de dividir para conquistar.

Dividir para conquistar não é um algoritmo específico, é uma forma de pensar o problema. Você reduz a entrada até chegar a um caso simples, resolve esse caso e combina os resultados. O caso base é sempre a menor entrada possível: um array vazio ou com um único elemento já está ordenado por definição.

O quicksort aplica essa ideia assim:

1. Escolha um elemento do array. Ele é o pivô.

2. Particione o array em dois subarrays: os menores que o pivô e os maiores que o pivô.

3. Aplique o quicksort recursivamente em cada subarray.

4. Combine: subarray esquerdo + pivô + subarray direito.

Com o array [33, 15, 10] e o 33 como pivô, o particionamento produz dois menores (15 e 10) de um lado e um subarray vazio do outro. O subarray de dois elementos é ordenado com uma troca simples, e o resultado final é [10, 15, 33]. Os subarrays saem do particionamento apenas particionados, não ordenados, e é a recursão que termina o serviço.

A escolha do pivô afeta o desempenho: um pivô ruim pode levar a partições desequilibradas e aproximar o algoritmo do pior caso. Nesse primeiro contato, usar o primeiro elemento do array como pivô já resolve o exemplo.

A biblioteca padrão da linguagem C inclui a função qsort, que é uma implementação do quicksort. Isso mostra que o algoritmo não é apenas acadêmico: ele está presente em código de produção há décadas.

Ordenar antes de buscar tem custo. O quicksort tem complexidade média O(n log n), e esse custo se soma ao da busca. Se você precisa fazer muitas buscas na mesma lista, ordenar uma vez e usar busca binária repetidamente costuma compensar. Para uma única busca, a busca linear pode ser mais simples e igualmente eficaz.

Se a lista não pode ser ordenada, a busca binária está fora de questão, e o caminho é outro: percorrer tudo com busca linear ou mudar a estrutura de dados. Uma tabela hash, por exemplo, troca a ordenação por um índice direto, ao custo de memória extra. O livro Entendendo Algoritmos cobre tabelas hash e funções hash no mesmo capítulo em que trata da busca binária, porque a decisão entre elas é de estrutura, não só de algoritmo.

Quando vale usar busca binária no dia a dia

O algoritmo não vive só em entrevista. Ele aparece sempre que existe dado ordenado e uma consulta por posição ou por valor.

• Logs indexados por timestamp: achar o primeiro erro depois de um horário específico.

• Autocomplete e busca incremental em listas ordenadas de termos.

• Paginação com salto direto para uma chave, sem varrer a tabela inteira.

• Consultas do tipo "primeiro protocolo maior que X" dentro de uma fila ordenada.

• Verificação de duplicidade em arrays já ordenados, comparando apenas vizinhos.

Do outro lado da linha, bibliotecas e bancos de dados já embutem a ideia. Bancos relacionais usam índices B-tree, que são uma generalização da busca binária. Buscar uma chave em uma tabela indexada não percorre linha por linha: desce a árvore em passos logarítmicos. Entender a busca binária é entender o que está embaixo desse índice.

Os casos em que ela não se aplica são tão importantes quanto: lista desordenada, busca por critério que não dá para comparar em ordem (uma busca por substring, por exemplo) e listas pequenas demais para o ganho compensar. Com 7 protocolos, qualquer abordagem resolve, e a binária só adiciona complexidade de leitura.

Se você quer revisar do zero: fontes e ferramentas

O material que originou este artigo é a live coding da Fernanda Kipper, do canal Dev Doido do canal do youtube, que começa com o problema, lê o capítulo de pesquisa binária do livro, escreve a força bruta e a busca binária em JavaScript e mede as duas com 1 milhão, 100 milhões e 1 bilhão de elementos.

Além do livro Entendendo Algoritmos, o canal tem um vídeo curto sobre o algoritmo de Dijkstra e sua relação com o Google Maps. A comunidade Crazystack também reúne material de apoio para quem está estudando algoritmos e estrutura de dados.

Para quem quer comparar implementações em outras linguagens, vale reproduzir os experimentos: gerar a lista, rodar a busca linear e a binária, medir com console.time e console.timeEnd e trocar a posição do alvo. A posição do alvo é a variável que mais muda o resultado da busca linear, e esse teste é o que transforma a teoria de complexidade em algo visível.

Perguntas frequentes sobre busca binária

Busca binária funciona em lista desordenada?

Não. A lógica depende da ordenação para descartar metade dos elementos com segurança. Se a lista não está ordenada, você pode ordená-la primeiro com um algoritmo como quicksort, ou usar busca linear.

Quantas comparações a busca binária faz no pior caso?

O número máximo é log₂ de n, arredondado para cima. Para 1 milhão de elementos, são cerca de 20 comparações. Para 240.000, são 18. Para 100 itens, 7.

Qual é a diferença entre busca binária e busca linear?

A busca linear percorre elemento por elemento e tem complexidade O(n). A busca binária divide o espaço pela metade a cada passo e tem complexidade O(log n). A busca binária exige lista ordenada, a linear não.

Medir tempo de execução é suficiente para comparar algoritmos?

Não. O tempo varia conforme hardware e carga da máquina. A análise de complexidade com notação Big O fornece uma medida independente do ambiente, e é o que permite afirmar que a busca binária em 1 milhão de itens é rápida em qualquer computador.

O que retornar quando o elemento não existe na lista?

A convenção comum é retornar -1, que indica posição inválida. Em linguagens com tipos opcionais, você pode retornar nulo ou um valor opcional vazio.

Por que a busca binária é imprevisível na busca linear e previsível nela mesma?

A busca linear depende de onde o alvo está: no fim da lista, percorre tudo. A busca binária tem teto calculado por log₂ de n, então o pior caso é conhecido antes de rodar o código.

A busca binária pode descartar o elemento que eu procuro?

Não, desde que a lista esteja ordenada. O valor do meio separa os menores dos maiores, então a metade descartada não contém o alvo. Se a lista não estiver ordenada, o descarte deixa de ser confiável.

Preciso ordenar a lista antes de cada busca?

Se a lista não muda, ordene uma vez e reutilize. Se cada busca acontece sobre uma lista nova, o custo de ordenar (O(n log n)) se soma ao da busca, e a busca linear pode ser mais simples.

A busca binária é sempre a melhor escolha?

Não. Em listas pequenas, o ganho é irrelevante e o código da busca linear é mais fácil de ler. A busca binária compensa quando n é grande e a lista já está ordenada.

Como o meio da lista é calculado dentro do laço?

Com Math.floor((inicio + fim) / 2). O floor garante um índice inteiro válido, e o intervalo ativo fica delimitado por inicio e fim, que são atualizados a cada iteração.

CTA: transforme o que você já explicou em vídeo em artigo

Se você explicou busca binária, quicksort ou qualquer outro fundamento em uma live ou vídeo no YouTube, esse conhecimento já existe — só não está em formato que o Google e as engines de resposta conseguem indexar bem. Um artigo estruturado com headings, tabelas e links para fontes primárias tem alcance diferente de um vídeo de 77 minutos.

O Skala Blog faz essa ponte: você cola a URL do vídeo, ele transcreve e gera um artigo pronto para revisão. Se você tem uma aula, uma entrevista ou uma explicação técnica gravada, cole o link no Skala Blog e veja o resultado.

Source video