If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

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 log2n, mas você também pode encontrá-lo escrito como lgn 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:
nlog2n
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. As funções logarítmicas são o inverso das exponenciais, que crescem muito rapidamente, portanto, se log2n=x, então n=2x. Por exemplo, como log2128=7, sabemos que 27=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 (log2128+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 29. Assim, podemos estimar que log21.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 é 221 (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 log2n 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.

Quer participar da conversa?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.