Algoritmos

Busca binária: o que é e como funciona (com exemplos)

Capa do artigo Busca binária: o que é e como funciona (com exemplos)
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como funciona a busca binária?
  2. Exemplo de busca binária passo a passo
  3. Busca binária em PHP, Python, C e JavaScript
  4. Dá para fazer busca binária com recursividade?
  5. Busca binária ou busca linear?
  6. Aí você pergunta: preciso escrever a busca binária toda vez?
  7. Agora é com você!

Busca binária é um algoritmo que encontra um valor dentro de um vetor ordenado dividindo o espaço de busca pela metade a cada passo. Em vez de olhar item por item, ela olha o valor do meio e descarta a metade onde o valor procurado não pode estar.

No artigo sobre a busca linear, você viu a busca que olha os valores um por um, do primeiro ao último. Hoje é a vez de uma busca muito mais rápida! E você verá que já conhece a busca binária desde criança, só não sabia o nome kkkk.

Como funciona a busca binária?

Pense no jogo de adivinhar um número de 1 a 100. Eu penso em um número e você tenta descobrir. A cada palpite respondo só “é maior” ou “é menor”. Você começaria pelo 1, depois 2, depois 3? Claro que não! Você chuta 50. Se eu disser “é maior”, você acabou de jogar fora metade dos números de uma vez só. Aí você chuta 75, e assim vai. Isso é busca binária!!!

História em quadrinhos em três quadros do jogo de adivinhar um número de 1 a 100: o palpite 50 recebe a resposta é maior, o palpite 75 recebe a resposta é menor e sobram os números de 51 a 74
O jogo de adivinhar um número: com dois palpites, sobram 24 dos 100 números.

O algoritmo repete sempre os mesmos três passos:

  • Olha o valor que está no meio do vetor.
  • Se for o valor procurado, achou. Fim.
  • Se não for, descarta a metade onde o valor não pode estar e repete com a metade que sobrou.

ATENÇÃO: a busca binária só funciona se o vetor estiver ordenado. Com os valores bagunçados, saber que o do meio é menor que o procurado não diz nada sobre o lado em que ele está. Sacou?

Exemplo de busca binária passo a passo

Vamos procurar o número 52 neste vetor de 10 posições:

Posição0123456789
Valor371218253140526780
Vetor ordenado usado no exemplo.

Repare que os valores já estão em ordem crescente: 3, 7, 12, 18 e assim por diante, até o 80. Não é por acaso! Vou repetir porque é importante: neste artigo, os dados já estão ordenados. Se não estivessem, teriam que ser ordenados antes da busca.

PassoInícioFimMeioValor do meioDecisão
10942525 é menor que 52: descarta a metade da esquerda
259752Achou! O 52 está na posição 7
Passo a passo da busca binária pelo número 52.
Diagrama da busca binária pelo número 52 em um vetor ordenado de dez posições, com a metade descartada a cada passo
A busca pelo 52: a cada comparação, metade do vetor é descartada.

Com duas comparações o 52 apareceu. Olhando item por item, desde o começo, seriam oito.

Ver a animação da busca binária, passo a passo
Animação da busca binária procurando o 52 em um vetor ordenado de dez posições: o meio é comparado, a metade da esquerda é descartada e o valor é encontrado na posição 7 com duas comparações
O mesmo exemplo em movimento: início, meio e fim andando, e a metade descartada ficando cinza.

Busca binária em PHP, Python, C e JavaScript

Veja em PHP:

<?php

function buscaBinaria(array $numeros, int $alvo): int
{
    $inicio = 0;
    $fim = count($numeros) - 1;

    while ($inicio <= $fim) {
        $meio = intdiv($inicio + $fim, 2);

        if ($numeros[$meio] === $alvo) {
            return $meio; // achou: devolve a posição
        }

        if ($numeros[$meio] < $alvo) {
            $inicio = $meio + 1; // o alvo está na metade da direita
        } else {
            $fim = $meio - 1; // o alvo está na metade da esquerda
        }
    }

    return -1; // não está no vetor
}

$numeros = [3, 7, 12, 18, 25, 31, 40, 52, 67, 80];

echo buscaBinaria($numeros, 52), PHP_EOL; // 7
echo buscaBinaria($numeros, 5), PHP_EOL;  // -1

Em Python:

def busca_binaria(numeros, alvo):
    inicio = 0
    fim = len(numeros) - 1

    while inicio <= fim:
        meio = (inicio + fim) // 2

        if numeros[meio] == alvo:
            return meio  # achou: devolve a posição

        if numeros[meio] < alvo:
            inicio = meio + 1  # o alvo está na metade da direita
        else:
            fim = meio - 1  # o alvo está na metade da esquerda

    return -1  # não está no vetor


numeros = [3, 7, 12, 18, 25, 31, 40, 52, 67, 80]

print(busca_binaria(numeros, 52))  # 7
print(busca_binaria(numeros, 5))   # -1

E em C:

#include <stdio.h>

int busca_binaria(int numeros[], int tamanho, int alvo) {
    int inicio = 0;
    int fim = tamanho - 1;

    while (inicio <= fim) {
        int meio = inicio + (fim - inicio) / 2;

        if (numeros[meio] == alvo) {
            return meio; // achou: devolve a posição
        }

        if (numeros[meio] < alvo) {
            inicio = meio + 1; // o alvo está na metade da direita
        } else {
            fim = meio - 1; // o alvo está na metade da esquerda
        }
    }

    return -1; // não está no vetor
}

int main(void) {
    int numeros[] = {3, 7, 12, 18, 25, 31, 40, 52, 67, 80};

    printf("%d\n", busca_binaria(numeros, 10, 52)); // 7
    printf("%d\n", busca_binaria(numeros, 10, 5));  // -1
    return 0;
}

E em JavaScript:

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

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

    if (numeros[meio] === alvo) {
      return meio; // achou: devolve a posição
    }

    if (numeros[meio] < alvo) {
      inicio = meio + 1; // o alvo está na metade da direita
    } else {
      fim = meio - 1; // o alvo está na metade da esquerda
    }
  }

  return -1; // não está no vetor
}

const numeros = [3, 7, 12, 18, 25, 31, 40, 52, 67, 80];
console.log(buscaBinaria(numeros, 52)); // 7
console.log(buscaBinaria(numeros, 5)); // -1

Reparou que nas quatro linguagens a ideia é a mesma? Duas variáveis marcam o começo e o fim do pedaço que ainda falta olhar, e a cada volta do laço esse pedaço cai pela metade. Vou repetir porque é importante: foque no conceito, e não na linguagem!

E não esqueça: em todos os exemplos, o vetor numeros já entra ordenado. Fiz o teste com os mesmos dez valores fora de ordem, [52, 3, 80, 12, 25, 7, 67, 18, 31, 40]: a busca pelo 52 devolveu -1, como se ele não estivesse lá, mesmo com o 52 logo na primeira posição. Vetor fora de ordem tem que ser ordenado antes da busca binária.

Um detalhe no C: o meio foi calculado como inicio + (fim - inicio) / 2. O resultado é o mesmo, mas essa forma evita que a soma inicio + fim passe do limite do tipo int em vetores muito grandes.

E um detalhe no JavaScript: a conta (inicio + fim) / 2 não joga fora a parte decimal. Com início 0 e fim 9, ela dá 4.5, e a posição 4.5 não existe no vetor. Testei sem o Math.floor: a busca pelo 52 devolveu -1, como se ele não estivesse lá, e sem nenhuma mensagem de erro. O Math.floor arredonda o meio para baixo, e a busca volta a funcionar.

Dá para fazer busca binária com recursividade?

Dá sim! Lembra do caso base e da chamada recursiva, do artigo sobre recursividade? Aqui o caso base é achar o valor ou não sobrar mais nada para procurar. A chamada recursiva é procurar de novo, só que na metade que sobrou. Veja em Python:

def busca_binaria(numeros, alvo, inicio, fim):
    if inicio > fim:
        return -1  # caso base: não sobrou nada para procurar

    meio = (inicio + fim) // 2

    if numeros[meio] == alvo:
        return meio  # caso base: achou

    if numeros[meio] < alvo:
        return busca_binaria(numeros, alvo, meio + 1, fim)

    return busca_binaria(numeros, alvo, inicio, meio - 1)


numeros = [3, 7, 12, 18, 25, 31, 40, 52, 67, 80]

print(busca_binaria(numeros, 52, 0, len(numeros) - 1))  # 7

Busca binária ou busca linear?

A busca que olha item por item é a busca linear (ou sequencial), a do artigo anterior. A diferença entre as duas aparece quando o vetor cresce. Veja o máximo de comparações de cada uma:

Tamanho do vetorBusca linearBusca binária
10104
1.0001.00010
1.000.0001.000.00020
1.000.000.0001.000.000.00030
Máximo de comparações no pior caso, quando o valor está no fim ou não existe.

Um bilhão de itens e no máximo 30 comparações!!! É por isso que se diz que a busca binária tem complexidade O(log n), enquanto a linear tem O(n). Se essa notação ainda é novidade para você, veja como calcular a complexidade de algoritmos.

Mas a busca linear tem a sua vantagem: ela funciona com o vetor em qualquer ordem. Se o vetor é pequeno ou não está ordenado, ela resolve.

Aí você pergunta: preciso escrever a busca binária toda vez?

No dia a dia, não. O Python, por exemplo, já traz o módulo bisect, que usa esse mesmo algoritmo de bisseção:

from bisect import bisect_left

numeros = [3, 7, 12, 18, 25, 31, 40, 52, 67, 80]

posicao = bisect_left(numeros, 52)

print(posicao)  # 7

Só um cuidado: a função bisect_left devolve o ponto de inserção, ou seja, a posição onde o valor está ou onde ele deveria entrar para manter a ordem. Se o valor pode não existir no vetor, confira se o que está naquela posição é mesmo o que você procurava.

Mesmo assim, escreva a busca binária na mão pelo menos uma vez. Quem entende como a ferramenta funciona por dentro sabe quando usar e sabe o que fazer quando ela não serve.

Agora é com você!

Um desafio para você usar a SUA cabeça: no vetor do exemplo, quantas comparações a busca binária faz até descobrir que o número 5 não está lá? Pegue papel e caneta e monte o passo a passo, igual à tabela que mostrei. Só depois rode o código para conferir.

Não peça a resposta pronta para ninguém antes de tentar, nem para a inteligência artificial. Errar e corrigir faz parte: é assim que o conceito entra de verdade. E você não precisa ser nenhum gênio para isso, só precisa praticar! A resposta eu conto no próximo artigo.

E por falar nele: você viu que a busca binária exige o vetor ordenado. E quando ele não está? Aí é preciso ordenar primeiro! No próximo artigo você vai conhecer o bubble sort, o algoritmo de ordenação mais simples de entender. Até lá!

Confiança Sempre!!!

Fontes:

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager. Como esse contêiner também carrega tags de publicidade, as estatísticas só são ativadas junto com Publicidade e marketing.

Exibem anúncios do Google AdSense e medem campanhas e e-mails: pixels da Meta e do TikTok e o Mautic.

Permite que o Google escolha anúncios com base nos seus interesses. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade e marketing.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.