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 2, n, 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, 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:
nlgn \lg n
10
21
42
83
164
325
646
1287
2568
5129
102410
1.048.57620
2.097.15221
Podemos visualizar essa mesma tabela na forma de um gráfico:
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 lgn=x \lg n = x , então n, equals, 2, start superscript, x, end superscript. For example, because lg128=7 \lg 128 = 7 , we know that 2, start superscript, 7, end superscript, equals, 128.
Quando 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, 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, 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.

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.