Baixe o app para aproveitar ainda mais
Prévia do material em texto
Busca binária Aprenda sobre a busca binária, uma forma de fazer uma busca eficiente em um array de itens com a diminuição do espaço de busca pela metade a cada vez. 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. https://pt.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search https://pt.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/a-guessing-game 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 https://pt.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/a-guessing-game 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 (26+80)/2 left parenthesis, 26, plus, 80, right parenthesis, slash, 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 min m, i, n ser a suposição razoável miníma desta partida, e a variável max max m, a, x será a suposição razoável máxima. A entrada do problema é o número n n 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 2. min=1 3. min=1 4. m, i, n, equals, 1 5. e 6. max=n 7. max=n 8. m, a, x, equals, n 9. . 10. Encontre a média de 11. max 12. max 13. m, a, x 14. e 15. min 16. min 17. m, i, n 18. , arredondando para baixo para que seja um inteiro. 19. Se você tiver adivinhado o número certo, pare. Você o encontrou! 20. Se o palpite foi muito baixo, defina o 21. min 22. min 23. m, i, n 24. como 1 a mais do que o palpite. 25. Se o palpite foi muito alto, defina o 26. max 27. max 28. m, a, x 29. como 1 a menos do que o palpite. 30. 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 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ê notou quantas etapas foram necessárias? Uma busca binária poderia ser mais eficiente. Como o array primes contém 25 números, os índices do array variam entre 0 e 24. Usando nosso pseudocódigo anterior, começamos fazendo min = 0 e max = 24. A primeira suposição na busca binária estaria, então no índice 12 (que é igual a (0+24)/2). primes[12] é igual a 67? Não, primes[12] é igual a 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. Desafio: Busca binária Implemente a busca binária (Se você não conhecer JavaScript, pode pular os desafios de código, ou pode fazer o curso de Introdução ao JS e voltar depois). Complete a função doSearch de modo que ela implemente uma busca binária, seguida pelo pseudocódigo abaixo (esse pseudocódigo foi descrito no artigo anterior): 1. Seja 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 guess como a média de max e min, arredondada para baixo (de modo que seja um número inteiro). 4. Se array[guess] for igual ao alvo, então pare. Você encontrou! Retorne guess. 5. Se o palpite for baixo demais, ou seja, array[guess] < target, então faça min = guess + 1. 6. Caso contrário, o palpite foi alto demais. Faça max = guess - 1. 7. Volte para o passo 2. Feita a implementação, retire os comentários da instrução Program.assertEqual() no final para verificar se o teste de asserção foi bem-sucedido. R: var doSearch = function(array, targetValue) { var min = 0; var max = array.length - 1; var guess; while(){ guess = ; if(===){ } else if(<){} else{ } } return -1; }; /* 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; 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); Como ele chega ao resultado? Para visualizar melhor como sua busca binária funciona, adicione uma instrução println()que exibe o palpite a cada etapa. Observação: você deve imprimir o índice do palpite, e não o valor do elemento para o qual ele aponta. Dica: var doSearch = function() { while() { println(); } }; /* 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; 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); Quanto tempo ele leva? Para ajudar na visualização do tempo que uma busca leva para ser feita, adicione uma instrução println() que mostra o número total de palpites necessários para encontrar o resultado. Sua função deve imprimir o número total de palpites somente quando ela tiver encontrado o alvo. Sua função não deve imprimir o número de palpites em todas as repetições do laço. Observação: uma busca binária pelo valor alvo 41 no array primes requer 1 palpite. DicaO que é isto? var doSearch = function() { while() { println(); } }; /* 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; 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); Teste! Adicione mais duas verificações, abaixo da verificação fornecida para 73, usando Program.assertEqual() para que seu algoritmo de busca encontre a resposta correta de forma consistente. Observe como ele chega ao resultado em cada vez. DicaO que é isto? Program.assertEqual(doSearch(primes, ), ); Program.assertEqual(doSearch(primes, ), ); /* 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; 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); Tempo de execução da busca binária Sabemos que a busca linear em um array de n elementos pode precisar fazer até n suposições. Você provavelmente já tem uma ideia intuitiva de que a busca binária faz menos suposições do que a busca linear. Você pode até ter percebido que a diferença entre o pior número possível de suposições da busca linear e da busca binária se torna mais evidente conforme o tamanho do array aumenta. Vamos ver como analisar o número máximo de suposições que a busca binária faz. A ideia principal é que quando a busca binária faz uma suposição incorreta, a porção do array que contém as suposições razoáveis se reduz pelo menos pela metade. Se a porção razoável tiver 32 elementos, então uma suposição incorreta a corta para ter no máximo 16. A busca binária divide o tamanho da porção razoável a cada suposição incorreta. Se começarmos com um array de comprimento 8, então as suposições incorretas reduzem o tamanho da porção razoável para 4, para 2 e então para 1. Quando a porção razoável contém apenas um elemento, não ocorrem mais suposições. A suposição para a porção com 1 elemento está correta ou incorreta, e então terminamos. Então, com um array de comprimento 8, a busca binária precisa de no máximo quatro suposições. O que você acha que aconteceria com um array de 16 elementos? Se você disse que a primeira suposição eliminaria pelo menos 8 elementos, de forma que restassem no máximo 8 elementos, você está começando a entender. Então, com 16 elementos, precisamos de no máximo cinco suposições. Você já deve estar começando a ver o padrão. Sempre que dobramos o tamanho do array, precisamos de, no máximo, mais uma suposição. Suponha que precisamos de no máximo m suposições para um array de comprimento n . Então, para um array de comprimento 2n, a primeira suposição reduz a porção razoável do array para o tamanho n, e no máximo m suposições terminam o processo, nos dando um total de no máximo m+1 m, plus, 1 suposições. Vamos examinar o caso geral de um array de comprimento n. Podemos expressar o número de suposições, no pior caso, como "o número de vezes que podemos reduzir pela metade, começando em n, até obter o valor 1, mais um". Mas é inconveniente escrever isso por extenso. Felizmente, há uma função matemática que representa o mesmo que o número de vezes que dividimos pela metade, começando em n, até obtermos o valor 1: o logaritmo de base 2 de n. Nós o escrevemos como lgn \lg, n. (You can learn more about logarithms here.) Aqui está uma tabela que mostra os logaritmos de base 2 de diversos valores de n: n n n \lg n lgn \lg, n 1 0 2 1 4 2 8 3 https://pt.khanacademy.org/math/algebra2/exponential-and-logarithmic-functions/introduction-to-logarithms/v/logarithms Podemos visualizar essa mesma tabela na forma de um gráfico: 16 4 32 5 64 6 128 7 256 8 512 9 1024 10 1.048.57 6 20 2.097.15 2 21 Dando zoom nos valores mais baixos de n: A função logarítmica cresce muito lentamente. Os logaritmos são o inverso dos exponenciais, que crescem muito rapidamente, então se \lg n = x lgn=x \lg, n, equals, x , então n = 2^x n=2 x n, equals, 2, start superscript, x, end superscript . For example, because \lg 128 = 7 lg128=7 \lg, 128, equals, 7 , we know that 2^7 = 128 2 7 =128 2, start superscript, 7, end superscript, equals, 128 . Quando n n n não é uma potência de 2, podemos simplesmente ir para a próxima maior potência de 2. Para qualquer array de comprimento 1000, a próxima maior potência de 2 é 1024, que é igual a 2^{10} 2 10 2, start superscript, 10, end superscript . Portanto, para um array de 1000 elementos, a busca binária precisaria de, no máximo, 11 (10 + 1) suposições. Para o catálogo estelar Tycho-2, com 2.539.913 estrelas, a próxima maior potência de 2 é 2^{22} 2 22 2, start superscript, 22, end superscript (que é 4.194.304), e precisaríamos de, no máximo, 23 suposições. Muito melhor que a busca linear! Compare as duas abaixo: No próximo tutorial, vamos ver como os cientistas da computação caracterizam os tempos de execução das buscas linear e binária, usando uma notação que destila a parte mais importante do tempo de execução e descarta as partes menos importantes. Quiz: Tempo de execução da busca binária Problema 1. 32 times se classificaram para a Copa do Mundo de 2014. Se os nomes dos times fossem colocados em ordem (em um array), quantos itens no array a busca binária teria que examinar para encontrar a localização de um time em particular no array, no pior caso? No máximo, 6 2. Qual é o lg(32), o logaritmo de 32 na base 2? 5 3. Você tem um array contendo os números primos de 2 a 311 em ordem: [2, 3, 5, 7, 11, 13, ..., 307, 311]. Há 64 itens no array. Cerca de quantos itens do array a busca binária teria que examinar antes de concluir que 52 não está no array, e portanto não é primo? 7 4. Em 2013, havia 193 países membros das Nações Unidas. Se os nomes desses países fosse ordenado alfabeticamente em um array, cerca de quantos nomes a busca binária teriaque examinar para encontrar um nome particular no array, no pior caso? Não mais que 9. 5. O "Catálogo da Vida" de 2014 contém cerca de 1580000 nomes de espécies. Se esses nomes fossem ordenados em um array, no pior caso, quanto tempo demoraria para que a busca binária encontrasse o nome de uma espécie em particular no array? No máximo, ele olharia para 22 nomes
Compartilhar