Vamos jogar um pequeno jogo para que você tenha uma ideia de como algoritmos diferentes para o mesmo problema podem ter desempenhos completamente diferentes. O computador vai selecionar aleatoriamente um número inteiro entre 1 e 16. Você deve adivinhar esse número fazendo suposições até encontrar o número que o computador escolheu:
Quando você descobrir o número, reflita sobre qual técnica você usou para decidir que número tentar a seguir.
Talvez você tenha tentado 1, 2, 3, 4 e assim por diante, até chegar ao número correto. Chamamos essa abordagem de busca linear, porque você tenta todos os números como se eles estivessem alinhados em fila. Isso funciona. Mas qual é o número máximo de tentativas de que você pode precisar? Se o computador escolher 30, você vai precisar de 30 tentativas. De novo, você pode ter muita sorte, o computador pode ter escolhido 1 e você vai encontrar o número na primeira tentativa. E na média? Se as chances do computador escolher qualquer número entre 1 e 30 forem iguais, então você precisará, em média, de 15 tentativas.
Mas você pode fazer algo mais eficiente do que apenas supor 1, 2, 3, 4… certo? Como o computador vai lhe dizer se uma suposição foi muito baixa, muito alta, ou correta, você pode começar tentando o 15. Se o número que o computador selecionou for menor que 15, então, por você saber que 15 é muito alto, pode desconsiderar todos os números de 15 a 30 a partir de uma análise. Se o número selecionado pelo computador for maior do que 15, então você pode desconsiderar os números de 1 a 15. De qualquer modo, você elimina aproximadamente metade dos números. Na sua próxima tentativa, elimine metade dos números restantes. Continue com isso, sempre eliminando metade dos números restantes. Vamos chamar essa abordagem de busca binária e não importa que número de 1 a 30 o computador tenha selecionado, você deve ser capaz de encontrá-lo no máximo em 5 tentativas com esta 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.
Carregando