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 $2n$‍, 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+1$‍ suposições.

Vamos analisar o caso geral de um array de tamanho $n$‍. Podemos expressar o número de chutes, no pior cenário, como o "número de vezes que podemos reduzir pela metade de forma repetida, começando em $n$‍, até conseguir o valor 1, mais um." Mas essa é uma forma inconveniente de escrever.

Felizmente, há uma função matemática que significa a mesma coisa que o número de vezes que reduzimos pela metade de forma repetida, começando em $n$‍, até conseguirmos o valor de 1: o logarítmo de $n$‍ na base 2, que normalmente é escrito como ${\log }_{2}n$‍, mas você também pode encontrá-lo escrito como $\lg n$‍ em textos de ciência da computação. (Quer fazer uma revisão sobre logaritmos? Saiba mais aqui).

Aqui está uma tabela que mostra os logaritmos de base 2 de diversos valores de $n$‍:

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. As funções logarítmicas são o inverso das exponenciais, que crescem muito rapidamente, portanto, se ${\log }_{2}n=x$‍, então $n=2^x$‍. Por exemplo, como ${\log }_{2}128=7$‍, sabemos que $2^7=128$‍.

Isso facilita o cálculo do tempo de execução de um algoritmo de busca binária em $n$‍ que é exatamente uma potência de 2. Se $n$‍ for 128, a busca binária vai precisar de, no máximo, 8 (${\log }_{2}128+1$‍) tentativas.

E se $n$‍ não for uma potência de 2? Nesse caso, podemos olhar a potência de 2 mais baixa. Para um array de tamanho 1.000, a potência de 2 mais próxima abaixo disso é 512, que é igual a $2^9$‍. Assim, podemos estimar que ${\log }_{2}1.000$‍ é um número maior que 9 e menor que 10, ou usar uma calculadora para verificar que é aproximadamente 9,97. Somar um a esse valor resulta em 10,97. No caso de um número decimal, arredondamos para baixo para encontrar o número verdadeiro de tentativas. Portanto, para um array de 1.000 elementos, uma busca binária precisaria de, no máximo, 10 tentativas.

Para o catálogo estelar Tycho-2, que contém 2.539.913 estrelas, a potência mais próxima abaixo disso é de 2 é $2^{21}$‍ (que é 2.097.152), então precisaríamos de, no máximo, 22 tentativas. Isso é muito melhor do que uma busca linear!

Compare $n$‍ versus ${\log }_{2}n$‍ 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.