If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Busca binária

A busca binária é um eficiente algoritmo para encontrar um item em uma lista ordenada de itens. Ela funciona dividindo repetidamente pela metade a porção da lista que deve conter o item, até reduzir as localizações possíveis a apenas uma. Nós usamos a busca binária em um jogo de adivinhação no tutorial introdutório.
Um dos modos mais comuns de se usar a busca binária é para encontrar um item em um array. Por exemplo, o catálogo estelar Tycho-2 contém informações sobre as 2.539.913 estrelas mais brilhantes na nossa galáxia. Suponha que você queira buscar por uma estrela em particular no catálogo, com base no nome da estrela. Se o programa examinou cada estrela do catálogo de estrelas em ordem começando com o primeiro nome, utilizando um algoritmo chamado busca linear, no pior caso, o computador pode ter examinado todas as 2,539,913 estrelas para encontrar a estrela que você está procurando. Se o catálogo estivesse organizado alfabeticamente pelos nomes das estrelas, a busca binária não teria que examinar mais do que 22 estrelas, mesmo no pior caso.
Os próximos artigos discutem como descrever o algoritmo cuidadosamente, como implementá-lo em JavaScript e como analisar sua eficiência.

Descrevendo a busca binária

Quando descrevemos um algoritmo para outro ser humano, uma descrição incompleta muitas vezes é o bastante. Alguns detalhes podem ter ficado de fora de uma receita para um bolo; a receita presume que você sabe como abrir o refrigerador para pegar os ovos e que você sabe como quebrar os ovos. As pessoas podem intuitivamente saber como encontrar detalhes faltantes, mas os programas de computador não podem. É por isso que precisamos descrever completamente os algoritmos de computador.
Para implementar um algoritmo em uma linguagem de programação, você precisa entender todos os detalhes do algoritmo. Quais são as entradas do problema? Quais são as saídas? Que variáveis devem ser criadas, e quais devem ser seus valores iniciais? Que etapas intermediárias devem ser realizadas para computar outros valores e para afinal computar a saída? Essas etapas repetem instruções que podem ser escritas de forma simplificada usando um laço?
Vamos ver como descrever cuidadosamente a busca binária. A ideia principal da busca binária é controlar a faixa atual de suposições razoáveis. Vamos dizer que estou pensando em um número entre um e 100, assim como o jogo de adivinhação. Se você já tiver tentado o 25 e eu tiver dito que meu número é maior, e já tiver tentado o 81 e eu tiver dito que meu número é menor, então os números na faixa de 26 a 80 são as únicas suposições razoáveis. Aqui, a seção vermelha da reta numérica contém as suposições razoáveis, e a seção preta as suposições que já foram descartadas:
A cada vez, você faz uma suposição que divide o conjunto de suposições razoáveis em duas faixas de tamanho aproximadamente igual. Se sua suposição não estiver correta, eu lhe direi se ela é alta ou baixa demais, e você vai pode eliminar cerca de metade das suposições razoáveis. Por exemplo, se o intervalo corrente de suposições razoáveis é de 26 a 80, você pode adivinhar o ponto do meio, (26+80)/2, ou 53. Então, se eu digo a você que 53 é muito alto, você pode eliminar todos os números de 53 a 80, deixando 26 a 52 como o novo intervalo de valores razoáveis, reduzindo pela metade o intervalo.
Para o jogo de adivinhação, podemos controlar o conjunto de suposições razoáveis usando algumas variáveis. Vamos deixar a variável min  ser a suposição razoável miníma desta partida, e a variável max  será a suposição razoável máxima. A entrada do problema é o número n, o maior número que seu oponente pode estar pensando. Assumimos que o menor valor possível é um, mas isto poderia ser facilmente modificado no algoritmo para pegar valores menores como uma segunda entrada.
Aqui está uma descrição passo a passo do uso de pesquisa binária para jogar o jogo de adivinhação:
  1. Defina que min=1 e max=n.
  2. Encontre a média de max e min, arredondando para baixo para que seja um inteiro.
  3. Se você tiver adivinhado o número certo, pare. Você o encontrou!
  4. Se o palpite foi muito baixo, defina o min como 1 a mais do que o palpite.
  5. Se o palpite foi muito alto, defina o max como 1 a menos do que o palpite.
  6. Volte ao passo dois.
Poderíamos fazer esse pseudocódigo ainda mais preciso descrevendo claramente as entradas e as saídas do algoritmo, além de esclarecer o que queremos dizer com instruções como "adivinhe um número" e "pare". Mas isso é o bastante por enquanto.
Na próxima vez, veremos como usar a busca binária em um array, e discutiremos como transformar descrições de algoritmos em códigos de verdade

Este conteúdo é uma colaboração entre os professores Thomas Cormen e Devin Balkcom da Dartmouth Computer Science e a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

  • Avatar piceratops seed style do usuário Stanley Sathler
    Vi o pessoal reclamando de não ter entendido o "min" e o "max" do exercício. Explicando de uma outra maneira, vamos lembrar o jogo da adivinhação:

    a) O jogo começa com 30 números disponíveis, de 1 a 30 (ou seja, [1, 2, 3, 4, ..., 30]). Como ainda não fizemos nenhuma jogada, o menor valor (mínimo, min) que podemos escolher é 0. Já o maior valor (máximo, max) que podemos escolher é 30.

    b) Seguindo os ensinamentos da busca binária, vamos "chutar" o número do meio: 15. Nisso, o programa me respondeu que o número premiado é MAIOR que 15. Se ele é MAIOR que 15, significa que os números de 1 a 15 não devem ser escolhidos. Afinal, o número premiado é MAIOR que 15. Sendo assim, o menor número (mínimo, min) que podemos escolher agora é 16. O maior continua sendo 30.

    c) Agora, só tenho disponível entre 16 e 30. Qual o número que fica na metade deste intervalo? (16 + 30) / 2 = 23. Pode conferir... 23 e 24 realmente estão no meio do intervalo. Chutamos então o 23. O jogo nos diz que o número premiado é MENOR que 23. Se o número premiado é MENOR que 23, significa que os números entre 23 e 30 já não devem ser mais escolhidos, correto? Sendo assim, o maior valor (máximo, max) que podemos escolher agora é 22.

    E por aí vai... (:
    (50 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar hopper jumping style do usuário Deivis Felipe Guerreiro
    Achei a iniciativa fantástica, ótimo trabalho, conteúdo claro e simples.
    (17 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar hopper cool style do usuário Deivison Takatu
    A busca binária pode ser encontrada em sites de pesquisa, como o Google?
    (10 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar starky seed style do usuário miteriolima
    muito bom gostei exercitando a mente
    (4 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar starky seedling style do usuário Glória Godoi
    Eu preciso de tanto este conteúdo(algorítimos) quanto programação, certo? Mas eu tenho que acabar um primeiro, antes de iniciar o outro?
    (3 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar piceratops seed style do usuário fabricio.balanaagulha
    É interessante pra mim estimula o raciocínio lógico porque já estudei informática porem dependendo do curso escolhido esta matéria é dispensável.
    (3 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar aqualine ultimate style do usuário weverton lobato
    #algoritmo de busca binaria
    from random import randint
    n_escolhido = randint(1,100)
    n_palpite = -1
    tentativas = 1
    max = 100
    min = 1
    while n_escolhido != n_palpite:
    n_palpite = int(input('digite um palpite: '))
    if n_palpite > max or n_palpite < min:
    print(f'opa, numero fora do intervalo {min} ou {max}.')
    tentativas += 1
    #continue reseta a iteração
    continue
    if n_escolhido == n_palpite:
    print('parabens!,voce encontrou')
    if tentativas == 1 :
    print('acertou de primeira! brabo demaix')
    else:
    print(f'tentativas:{tentativas}')
    elif n_escolhido > n_palpite:
    print('o numero é maior')
    min = n_palpite + 1
    tentativas += 1
    print(f'o numero está entre {min} e {max}')
    else:
    print('o numero é menor')
    max = n_palpite - 1
    print(f'o numero está entre {min} e {max}')
    tentativas += 1

    #========================================================
    #escrito em python por weverton lobato da silva
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar leaf green style do usuário Kaio Lucas
    Ótimo conteúdo, preciso e bem didatico.
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário Rye Takeda
    Na descrição do pseudocódigo não foi considerada a possibilidade em reduzir as possibilidades pela metade correto?
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário Murilo Monteiro
    Teria como publicar esses textos em português ?
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.