Para utilizar a Khan Academy, você precisa atualizar seu navegador. Selecione uma das opções abaixo para começar a atualização.
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.
Ciência da Computação.
Unidade 1: Aula 2.
Implementação de busca binária de um array.
Tempo de execução da busca binária.
Tempo de execução da busca binária.
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 (26+80)/2 ( 2 6 + 8 0 ) / 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 m i n min m i n m, i, n ser a suposição razoável miníma desta partida, e a variável m a x max m a x m, a, x será a suposição razoável máxima. A entrada do problema é o número n 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:
Defina que m i n = 1 min=1 m i n = 1 m, i, n, equals, 1 e m a x = n max=n m a x = n m, a, x, equals, n . Encontre a média de m a x max m a x m, a, x e m i n min m i n m, i, n , arredondando para baixo para que seja um inteiro. Se você tiver adivinhado o número certo, pare. Você o encontrou! Se o palpite foi muito baixo, defina o m i n min m i n m, i, n como 1 a mais do que o palpite. Se o palpite foi muito alto, defina o m a x max m a x m, a, x como 1 a menos do que o palpite. 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?
Publicado há há 6 anos. Link direto para a postagem “Vi o pessoal reclamando d. ” de 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.
