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

Um jogo de adivinhação

Vamos jogar um joguinho para dar a você uma ideia de como algoritmos diferentes para o mesmo problema podem ter eficiências totalmente diferentes. O computador vai selecionar aleatoriamente um número inteiro de 1 a 15. Você vai tentar adivinhar o número até encontrar aquele que foi selecionado pelo computador, e o computador lhe dirá a cada vez se seu palpite foi muito alto ou muito baixo:
Quando você descobrir o número, reflita sobre qual técnica você usou para decidir que número tentar a seguir.
Talvez você tenha chutado 1, depois 2, depois 3, depois 4 e assim por diante, até adivinhar o número certo. Chamamos essa abordagem de busca linear, porque você supõe todos os números como se estivessem alinhados em uma fileira. Isso funcionaria. Mas qual é o maior número de suposições que você pode precisar fazer? Se o computador selecionar 15, você vai precisar de 15 suposições. Então, novamente, você pode ter muita sorte, que seria quando o computador seleciona o número 1 e você obtém o número em sua primeira suposição. E quanto à média? Se o computador tiver a mesma probabilidade de selecionar qualquer número de 1 a 15, então, em média, você vai precisar de 8 suposições.
Mas você poderia fazer algo mais eficiente do que apenas chutar 1, 2, 3, 4, …, certo? Como o computador informa se um palpite é muito baixo, muito alto ou correto, você pode começar pelo palpite de 8. Se o número que o computador selecionou for menor que 8, então como você sabe que 8 é muito alto, você pode desconsiderar todos os números de 8 a 15. Se o número selecionado pelo computador for maior que 8, você pode eliminar de 1 a 8. De qualquer forma, você pode eliminar metade dos números. Em seu próximo palpite, elimine metade dos números restantes. Continue, sempre eliminando metade dos números restantes.
Chamamos essa abordagem das metades de busca binária e, não importa qual número de 1 a 15 o computador tenha selecionado, você poderá encontrar o número em no máximo 4 tentativas com essa técnica.
Agora, tente isso com um número entre 1 e 300. Você não deve precisar de mais de 9 tentativas.
De quantas tentativas você precisou para encontrar o número nessa vez? Por que você nunca deve precisar de mais de 9 tentativas? (Você pode pensar em uma explicação matemática?)?
Vamos retornar à busca binária, e vamos ver como você pode usá-la para buscar com eficiência um item em um array JavaScript. Mas, primeiro, vamos examinar um algoritmo para um problema mais complicado.
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?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.