Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Conteúdo principal

Implementação de busca binária de um array

Vamos ver como pensar na busca binária em um array organizado. Sim, o JavaScript proporciona métodos para determinar se um dado elemento está em um array e, se estiver, sua posição (assim como muitas linguagens de programação), mas queremos implementar isso nós mesmos, para entender como implementar métodos desse tipo. Aqui está um array JavaScript dos 25 primeiros números primos, em ordem:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
Suponha que desejemos saber se o número 67 é primo. Se 67 estiver no array, então ele é primo.
Podemos também querer saber quantos números primos são menores que 67. Se descobrirmos a posição do número 67 no array, podemos usar essa informação para descobrir quantos números primos menores que ele existem.
A posição de um elemento em um array é conhecida como seu índice. Os índices dos arrays começam em 0 e são contados de forma crescente. Se um elemento estiver no índice 0, ele é o primeiro elemento do array. Se um elemento estiver no índice 3, então ele tem elementos 3 antes dele no array.
Examinando o exemplo abaixo, podemos ler o array de números primos da esquerda para a direita, um por vez, até descobrirmos o número 67 (na caixa rosa) e vermos que ele está no índice 18 do array. Olhar para os números na ordem é uma busca linear.
Uma vez que sabemos que o número primo 67 está no índice 18, podemos identificá-lo como um primo. Também podemos identificar rapidamente que há 18 elementos antes do 67 no array, o que significa que há 18 números primos menores que 67.
Você viu quantos movimentos foram necessários? Uma busca binária pode ser mais eficiente. Como o array primes contém 25 números, os índices no array variam de 0 até 24. Com base nas instruções do passo a passo do artigo anterior, começamos definindo min = 0 e max = 24. O primeiro palpite na busca binária seria, portanto, no índice 12 (que é (0 + 24) / 2). O primes[12] é igual a 67? Não, primes[12] é 41.
O índice que estamos procurando é maior ou menor do que 12? Como os valores no array estão em ordem crescente, e 41 < 67, o valor 67 deve estar à direita do índice 12. Em outras palavras, o índice que estamos tentando encontrar deve ser maior do que 12. Atualizamos o valor de min para 12 + 1, ou 13, e mantemos o max igual a 24.
Qual é a próxima suposição de índice? A média entre 13 e 24 é 18,5, que podemos arredondar para 18, já que os índices dos arrays devem ser números inteiros. Descobrimos que primes[18] é 67.
O algoritmo da busca binária para neste ponto, já que encontrou a resposta. Foram necessárias apenas duas tentativas em vez das 19 tentativas de que a busca linear precisaria. Você pode acompanhar o processo novamente na visualização abaixo:

Pseudocódigo

Acabamos de descrever o algoritmo da busca binária em português, acompanhando um exemplo. Este é um modo de fazer isso, mas uma explicação em linguagem humana pode variar em qualidade. Ela pode ser curta demais ou longa demais, e, mais importante, ela nem sempre é tão precisa quanto deveria. Poderíamos pular isso para mostrar a você uma busca binária em uma linguagem de programação como JavaScript ou Python, mas programas contêm muitos detalhes - devido a requerimentos impostos pela linguagem de programação, ou porque eles devem lidar com erros causados por dados corrompidos, ou falhas do sistema - e isso pode dificultar a compreensão do algoritmo fundamental se estudarmos apenas o código. É por isso que preferimos descrever os algoritmos em algo chamado pseudocódigo, que mistura português com características que se vê em linguagens de programação.
Aqui está um pseudocódigo para a busca binária, modificado para realizar uma busca em um array. As entradas são o array, que chamamos de array; o número n de elementos no array; e o alvo (target), número buscado primeiramente. A saída é o índice do alvo no array.
  1. Defina min = 0 e max = n-1.
  2. Calcule chute como sendo a média entre max e min, arrendonde para baixo (então será um número inteiro).
  3. Se array[chute] for igual ao alvo, então pare. Você o encontrou! Retorne chute.
  4. Se o chute for muito baixo, ou seja, array[chute] < alvo, então defina min = chute + 1.
  5. Caso contrário, o chute foi muito alto. Defina max = chute - 1.
  6. Volte para o passo 2.

Implementação do pseudocódigo

Vamos alternar entre português, pseudocódigo e JavaScript nesses tutoriais, dependendo da situação. Como programador, você deve aprender a entender o pseudocódigo e ser capaz de convertê-lo na sua linguagem escolhida - então, embora estejamos usando JavaScript aqui, deve ser simples para você implementar pseudocódigo em outras linguagens.
Como poderíamos converter esse pseudocódigo em um programa JavaScript? Devemos criar uma função, porque estamos escrevendo um código que aceita uma entrada e retorna uma saída, e queremos que esse código seja reutilizável para diferentes entradas. Os parâmetros da função — vamos chamá-la binarySearch — serão o array e o valor alvo (target), e o valor de retorno da função será o índice da posição onde o valor alvo foi encontrado.
Agora, vamos examinar o corpo principal da função, e decidir como implementá-lo. A etapa 6 diz para voltar para a etapa 2. Isso parece ser um laço. Ele deve ser um laço for ou um laço while? Se você realmente quisesse usar um laço for, poderia fazê-lo, mas os índices supostos pela busca binária não estão na ordem sequencial que o laço for torna-se conveniente. Primeiro, podemos selecionar o índice 12, então o 18, com base em algumas computações. Então, um laço while é a melhor opção.
Há também uma etapa importante faltando nesse pseudocódigo que não era importante no jogo de adivinhação, mas é importante na busca binária de um array. O que deve acontecer se o número que você está procurando não estiver no array? Vamos começar descobrindo qual índice a função binarySearch deve retornar neste caso. O índice deve ser um número que não pode ser válido no array. Vamos usar -1, já que este não pode ser um índice válido em nenhum array. (Na verdade, qualquer número negativo servirá.)
O número alvo não estará no array se não houver mais possíveis chutes. Em nosso exemplo, suponha que estamos procurando pelo alvo número 10 no array primes. Se o 10 estivesse lá, ele estaria entre os números 7 e 11, que estão nos índices 3 e 4. Se você rastrear os índices dos valores para min e max assim como a função binarySearch faz, você descobriria que em algum momento eles estariam no ponto onde min é igual a 3 e max é igual a 4. O chute é então o índice 3 (como (3 + 4) / 2 é igual a 3,5, e arredondamos para baixo), e primes[3] é menor que 10, desta forma, min se torna 4. Com ambos, min e max valendo 4, o chute deve ser o índice 4, e primes[4] é maior que 10. Agora max se torna 3. O que isso significa, min ser igual a 4 e max ser igual a 3? Isso significa que os únicos possíveis chutes são no mínimo 4 e no máximo 3. Não existe esse número no array! Neste ponto, podemos concluir que o alvo 10, não está no array primes, e a função binarySearch retornaria -1. Em geral, uma vez que max se torna estritamente menor que min, nós sabemos que o número alvo não está no array ordenado. A seguir está o pseudocódigo modificado para a busca binária que lida com o caso em que o número alvo não está no array:
  1. Defina min = 0 e max = n-1.
  2. Se max < min, então pare: o alvo não está presente no array. Retorne -1.
  3. Calcule o chute como sendo a média entre max e min, arredondando para baixo (então será um número inteiro).
  4. Se array[chute] for igual ao alvo, então pare. Você o encontrou! Retorne chute.
  5. Se o chute foi muito baixo, ou seja, array[chute] < alvo, então defina min = guess + 1.
  6. Caso contrário, o chute foi muito alto. Defina max = guess - 1.
  7. Volte para o passo 2.
Agora que analisamos o pseudocódigo juntos, você vai tentar implementar a busca binária por conta própria. Tudo bem dar uma olhada no pseudocódigo - de fato, isso é bom, porque assim você vai compreender melhor o que significa converter um pseudocódigo em um programa.
Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

  • Avatar blobby green style do usuário Gabriel Santos
    A maioria dessas lições são um texto gingatesco, com um monte de terminologias e sem nenhum video ou animação do tipo para facilitar a elucidação. Melhorem isso, coloquem mais videos
    (21 votos)
    Avatar Default Khan Academy avatar do usuário
    • Avatar leaf green style do usuário Jhonatan Martins
      Isso é uma aula de algorítimos e não de "lógica de programação" creio que você está na aula errada meu caro. É importante primeiro assistir uma introdução a lógica da programação aí então você veria como esse artigo e aula está muito bem escrito e muito bem aproveitável para o tema.
      (12 votos)
  • Avatar duskpin seedling style do usuário Henri
    talvez uma pequena plataforma onde se possa usar os codigos e testa-los, seja o que falta
    (21 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar orange juice squid orange style do usuário Leo Labrada
    Porque a função while e não a for?
    (20 votos)
    Avatar Default Khan Academy avatar do usuário
    • Avatar piceratops ultimate style do usuário Rosemary Sumitani
      O for é interessante em uma abordagem linear com uma variável, pelo fato de ter inicialização, verificação e atualização, já o while só tem a verificação e dentro do escopo dela pode se atualizar diversas variáveis se atenderem certa condição, mostrado no pseudocódigo. Inserir várias variáveis de forma condicional na atualização do for deixaria o código difícil de ler.
      (30 votos)
  • Avatar blobby green style do usuário triplox71
    um pouco dificil de entender
    (9 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar leaf red style do usuário Peuzyn
    Queria tanto que isso fosse traduzido...
    (4 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar duskpin seedling style do usuário Matheus Oliveira Santana
    Achei bem interessante o conteudo da binaria mas um pouco complicado para intender
    (4 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar leafers seed style do usuário alanferrari33
    Como é que faz o desafio de busca binária?
    Não entendi como funciona o preenchimento das lacunas na dica que é dada, fiquei totalmente perdido sem saber o que fazer ou por onde começar.
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar starky ultimate style do usuário ZaveriTom
    ainda não entendi muito bem o que o array faz
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário danielsantosdj
    Procure seguir cada etapa , sem muita consulta.
    Fato é que a estrutura dos códigos você vai dominar com a prática.
    Lembre-se de que isso é um exercício, então todos aqui são estudantes e nâo professores.

    Segue abaixo para ajuda

    ########

    /* Returns either the index of the location in the array,
    or -1 if the array did not contain the targetValue */
    var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;
    var i=0;

    while ( min < max+1 ){

    i++;
    guess = floor((min+max)/2);

    if ( array[guess] === targetValue)

    {
    println(guess);
    println(i);
    return guess;
    }

    else if (targetValue>array[guess])

    {
    min = guess +1;
    println(guess);
    }

    else { max = guess -1;}
    println(guess);

    }

    return -1;
    };

    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

    var result = doSearch(primes, 73);
    println("Found prime at index " + result);

    Program.assertEqual(doSearch(primes, 73), 20);
    Program.assertEqual(doSearch(primes, 61), 17);
    Program.assertEqual(doSearch(primes, 2), 0);
    (2 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar duskpin ultimate style do usuário Giovanni Elias
    Não consigo fazer a busca binária alguém me ajuda? Já vi comentários de resposta mas não entendi. :(
    (2 votos)
    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.