Conteúdo principal
Ciência da Computação
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
.- Defina
min = 0
emax = n-1
. - Calcule
chute
como sendo a média entremax
emin
, arrendonde para baixo (então será um número inteiro). - Se
array[chute]
for igual aoalvo
, então pare. Você o encontrou! Retornechute
. - Se o chute for muito baixo, ou seja,
array[chute] < alvo
, então definamin = chute + 1
. - Caso contrário, o chute foi muito alto. Defina
max = chute - 1
. - 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:- Defina
min = 0
emax = n-1
. - Se
max < min
, então pare: oalvo
não está presente noarray
. Retorne-1
. - Calcule o
chute
como sendo a média entremax
emin
, arredondando para baixo (então será um número inteiro). - Se
array[chute]
for igual aoalvo
, então pare. Você o encontrou! Retornechute
. - Se o chute foi muito baixo, ou seja,
array[chute] < alvo
, então definamin = guess + 1
. - Caso contrário, o chute foi muito alto. Defina
max = guess - 1
. - 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?
- talvez uma pequena plataforma onde se possa usar os codigos e testa-los, seja o que falta(20 votos)
- Porque a função while e não a for?(20 votos)
- 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)
- 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(20 votos)
- 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.(9 votos)
- um pouco dificil de entender(9 votos)
- Queria tanto que isso fosse traduzido...(4 votos)
- Achei bem interessante o conteudo da binaria mas um pouco complicado para intender(4 votos)
- 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) - ainda não entendi muito bem o que o array faz(2 votos)
- 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) - Não consigo fazer a busca binária alguém me ajuda? Já vi comentários de resposta mas não entendi. :((2 votos)