Tempo de execução da busca binária

Sabemos que a busca linear em um array de $n$n elementos pode precisar fazer até $n$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$m suposições para um array de comprimento $n$n. Então, para um array de comprimento $2n$2, n, a primeira suposição reduz a porção razoável do array para o tamanho $n$n, e no máximo $m$m suposições terminam o processo, nos dando um total de no máximo $m+1$m, plus, 1 suposições.

Vamos analisar o caso geral de um array de tamanho $n$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$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$n, até conseguirmos o valor de 1: o logarítmo de $n$n na base 2, que normalmente é escrito como $\log_2 n$log, start base, 2, end base, n, mas você também pode encontrá-lo escrito como $\lg n$\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$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$log, start base, 2, end base, n, equals, x, então $n = 2^x$n, equals, 2, start superscript, x, end superscript. Por exemplo, como $\log_2 128 = 7$log, start base, 2, end base, 128, equals, 7, sabemos que $2^7 = 128$2, start superscript, 7, end superscript, equals, 128.

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

E se $n$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}$2, start superscript, 9, end superscript. Assim, podemos estimar que $\log_2 1.000$log, start base, 2, end base, 1, point, 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}$2, start superscript, 21, end superscript (que é 2.097.152), então precisaríamos de, no máximo, 22 tentativas. Isso é muito melhor do que uma busca linear!

Compare $n$n versus $\log _{2} n$log, start base, 2, end base, 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.