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?
Qual diferença entre o sistema de procura binário e línea?(11 votos)
O sistema de procura linear realiza tentativas um a um de encontrar o número buscado.
ex: em uma lista de 1 a 10 onde escolhemos o número 7 por exemplo, o sistema de busca linear vai realizar 7 buscar até encontrar o número escolhido, ou seja, começando busca 1,2,3,4,5,6 e finalmente encontrando o 7 na sétima tentativa.
Já o método de busca binária, quebra a mesma lista de 10 números (1,2,3,4,5,6,7,8,9,10) em duas partes, supondo que o número buscado está exatamente no meio. Logo "chutamos o número 5", se não for , sabemos que se o número não for a escolha certa e se for maior que a nossa escolha, descartamos os números de 1 a 5. Agora temos a lista de 6 a 10. Novamente dividimos ela por dois. E assim sucessivamente..(52 votos)
como se poderia tentar um efeito semelhante se não tivéssemos um feedback do system , apenas uma resposta de sim ou não do sistema.Sem indicações extras?(27 votos)- Acredito que a única resposta correta envolve potência de base dois, já que o texto afirma que trata-se de números binários. Uma resposta em função de logaritmo na base dois seria muito perspicaz, visto que o valor encontrado representa a potência necessária para se escrever o número 300 utilizando a base 2. Portanto, a parte inteira pode representar o expoente de 2 necessário para a dividir 300 por 2 elevando a esse inteiro e obter um número maior que 1. Ou seja, se utilizarmos um número maior, estaremos dividindo uma resposta em duas partes, coisa que não é permitida pelo problema.(9 votos)
Para quem não conseguiu: Pegue o menor número, some com o maior e divida por 2. E assim vai suscetivamente até o resultado. Deste modo, na pior das hipóteses terá realizado 9 movimentos.(5 votos)
Busca linear é obedecer uma ordem sequencial, enquanto a busca binária da liberdade para uma escolha aleatória e mais racional. Estou Certo?(1 voto)
Não está. Busca binária é um método específico em que se intercalam múltiplos de 2(do 1 ao 15, por exemplo, começamos com o 8, se for menor colocamos o 4, de forma a sempre dividir os números restantes em dois).(6 votos)
- devido a distancia que se encontram um do outro(3 votos)
- eta eu pensei que era de ciencias de animais e acabei levando uma pronca da minha mae kkk(3 votos)
- Em quais outras areas do desenvolvimento humano a busca binaria traz mais vantagens(3 votos)
o que seria um array JavaScript?(3 votos)- não entendiii
como faço?(2 votos)
mas vc n entendeu oq exatamente?(3 votos)