Busca binária

Prévia do material em texto

Busca binária 
 
Aprenda sobre a busca binária, uma forma de fazer uma busca eficiente em um 
array de itens com a diminuição do espaço de busca pela metade a cada vez. 
A busca binária é um eficiente algoritmo para encontrar um item em 
uma lista ordenada de itens. Ela funciona dividindo repetidamente 
pela metade a porção da lista que deve conter o item, até reduzir 
as localizações possíveis a apenas uma. Nós usamos a busca 
binária em um ​jogo de adivinhação​ no tutorial introdutório. 
Um dos modos mais comuns de se usar a busca binária é para 
encontrar um item em um array. Por exemplo, o catálogo estelar 
Tycho-2 contém informações sobre as 2.539.913 estrelas mais 
brilhantes na nossa galáxia. Suponha que você queira buscar por 
uma estrela em particular no catálogo, com base no nome da 
estrela. Se o programa examinou cada estrela do catálogo de 
estrelas em ordem começando com o primeiro nome, utilizando um 
algoritmo chamado ​busca linear​, no pior caso, o computador pode 
ter examinado todas as 2,539,913 estrelas para encontrar a estrela 
que você está procurando. Se o catálogo estivesse organizado 
alfabeticamente pelos nomes das estrelas, a ​busca binária​ não 
teria que examinar mais do que 22 estrelas, mesmo no pior caso. 
Os próximos artigos discutem como descrever o algoritmo 
cuidadosamente, como implementá-lo em JavaScript e como 
analisar sua eficiência. 
https://pt.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search
https://pt.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/a-guessing-game
Descrevendo a busca binária 
Quando descrevemos um algoritmo para outro ser humano, uma 
descrição incompleta muitas vezes é o bastante. Alguns detalhes 
podem ter ficado de fora de uma receita para um bolo; a receita 
presume que você sabe como abrir o refrigerador para pegar os 
ovos e que você sabe como quebrar os ovos. As pessoas podem 
intuitivamente saber como encontrar detalhes faltantes, mas os 
programas de computador não podem. É por isso que precisamos 
descrever completamente os algoritmos de computador. 
Para implementar um algoritmo em uma linguagem de 
programação, você precisa entender todos os detalhes do 
algoritmo. Quais são as entradas do problema? Quais são as 
saídas? Que variáveis devem ser criadas, e quais devem ser seus 
valores iniciais? Que etapas intermediárias devem ser realizadas 
para computar outros valores e para afinal computar a saída? 
Essas etapas repetem instruções que podem ser escritas de forma 
simplificada usando um laço? 
Vamos ver como descrever cuidadosamente a busca binária. A 
ideia principal da busca binária é controlar a faixa atual de 
suposições razoáveis. Vamos dizer que estou pensando em um 
número entre um e 100, assim como o ​jogo de adivinhação​. Se 
você já tiver tentado o 25 e eu tiver dito que meu número é maior, e 
já tiver tentado o 81 e eu tiver dito que meu número é menor, então 
os números na faixa de 26 a 80 são as únicas suposições 
razoáveis. Aqui, a seção vermelha da reta numérica contém as 
https://pt.khanacademy.org/computing/computer-science/algorithms/intro-to-algorithms/a/a-guessing-game
suposições razoáveis, e a seção preta as suposições que já foram 
descartadas: 
 
A cada vez, você faz uma suposição que divide o conjunto de 
suposições razoáveis em duas faixas de tamanho 
aproximadamente igual. Se sua suposição não estiver correta, eu 
lhe direi se ela é alta ou baixa demais, e você vai pode eliminar 
cerca de metade das suposições razoáveis. Por exemplo, se o 
intervalo corrente de suposições razoáveis é de 26 a 80, você pode 
adivinhar o ponto do meio, 
(26+80)/2 
(26+80)/2 
left parenthesis, 26, plus, 80, right parenthesis, slash, 2 
, ou 53. Então, se eu digo a você que 53 é muito alto, você pode 
eliminar todos os números de 53 a 80, deixando 26 a 52 como o 
novo intervalo de valores razoáveis, reduzindo pela metade o 
intervalo. 
 
Para o jogo de adivinhação, podemos controlar o conjunto de 
suposições razoáveis usando algumas variáveis. Vamos deixar a 
variável 
min 
min 
m, i, n 
 ser a suposição razoável miníma desta partida, e a variável 
max 
max 
m, a, x 
 será a suposição razoável máxima. A ​entrada​ do problema é o 
número 
n 
n 
n 
, o maior número que seu oponente pode estar pensando. 
Assumimos que o menor valor possível é um, mas isto poderia ser 
facilmente modificado no algoritmo para pegar valores menores 
como uma segunda entrada. 
Aqui está uma descrição passo a passo do uso de pesquisa binária 
para jogar o jogo de adivinhação: 
1. Defina que 
2. min=1 
3. min​=1 
4. m, i, n, equals, 1 
5. e 
6. max=n 
7. max​=​n 
8. m, a, x, equals, n 
9. . 
10. Encontre a média de 
11. max 
12. max 
13. m, a, x 
14. e 
15. min 
16. min 
17. m, i, n 
18. , arredondando para baixo para que seja um inteiro. 
19. Se você tiver adivinhado o número certo, pare. Você o 
encontrou! 
20. Se o palpite foi muito baixo, defina o 
21. min 
22. min 
23. m, i, n 
24. como 1 a mais do que o palpite. 
25. Se o palpite foi muito alto, defina o 
26. max 
27. max 
28. m, a, x 
29. como 1 a menos do que o palpite. 
30. Volte ao passo dois. 
Poderíamos fazer esse pseudocódigo ainda mais preciso 
descrevendo claramente as entradas e as saídas do algoritmo, 
além de esclarecer o que queremos dizer com instruções como 
"adivinhe um número" e "pare". Mas isso é o bastante por 
enquanto. 
Na próxima vez, veremos como usar a busca binária em um array, 
e discutiremos como transformar descrições de algoritmos em 
códigos de verdade 
Implementação de busca binária de um 
array 
 
Vamos ver como pensar na busca binária em um array organizado. 
Sim, o JavaScript proporciona métodos para determinar se um 
dado elemento está em um array e, se estiver, sua posição (assim 
como muitas linguagens de programação), mas queremos 
implementar isso nós mesmos, para entender como implementar 
métodos desse tipo. Aqui está um array JavaScript dos 25 
primeiros números primos, em ordem: 
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; 
Suponha que desejemos saber se o número 67 é primo. Se 67 
estiver no array, então ele é primo. 
Podemos também querer saber quantos números primos são 
menores que 67. Se descobrirmos a posição do número 67 no 
array, podemos usar essa informação para descobrir quantos 
números primos menores que ele existem. 
A posição de um elemento em um array é conhecida como seu 
índice. Os índices dos arrays começam em 0 e são contados de 
forma crescente. Se um elemento estiver no índice 0, ele é o 
primeiro elemento do array. Se um elemento estiver no índice 3, 
então ele tem elementos 3 antes dele no array. 
Examinando o exemplo abaixo, podemos ler o array de números 
primos da esquerda para a direita, um por vez, até descobrirmos o 
número 67 (na caixa rosa) e vermos que ele está no índice 18 do 
array. Olhar para os números na ordem é uma ​busca linear​. 
Uma vez que sabemos que o número primo 67 está no índice 18, 
podemos identificá-lo como um primo. Também podemos identificar 
rapidamente que há 18 elementos antes do 67 no array, o que 
significa que há 18 números primos menores que 67. 
Você notou quantas etapas foram necessárias? Uma busca binária 
poderia ser mais eficiente. Como o array ​primes​ contém 25 
números, os índices do array variam entre 0 e 24. Usando nosso 
pseudocódigo anterior, começamos fazendo ​min​ = 0 e ​max​ = 24. A 
primeira suposição na busca binária estaria, então no índice 12 
(que é igual a (0+24)/2). ​primes[12]​ é igual a 67? Não, 
primes[12]​ é igual a 41. 
 
O índice que estamos procurando é maior ou menor do que 12? 
Como os valores no array estão em ordem crescente, e 41 < 67, o 
valor 67 deve estar à direita do índice 12. Em outras palavras, o 
índice que estamos tentando encontrar deve ser maior do que 12. 
Atualizamos o valor de ​min​ para 12+ 1, ou 13, e mantemos o ​max 
igual a 24. 
 
Qual é a próxima suposição de índice? A média entre 13 e 24 é 
18,5, que podemos arredondar para 18, já que os índices dos 
arrays devem ser números inteiros. Descobrimos que ​primes[18] 
é 67. 
 
O algoritmo da busca binária para neste ponto, já que encontrou a 
resposta. Foram necessárias apenas duas tentativas em vez das 
19 tentativas de que a busca linear precisaria. Você pode 
acompanhar o processo novamente na visualização abaixo: 
Pseudocódigo 
Acabamos de descrever o algoritmo da busca binária em 
português, acompanhando um exemplo. Este é um modo de fazer 
isso, mas uma explicação em linguagem humana pode variar em 
qualidade. Ela pode ser curta demais ou longa demais, e, mais 
importante, ela nem sempre é tão precisa quanto deveria. 
Poderíamos pular isso para mostrar a você uma busca binária em 
uma linguagem de programação como JavaScript ou Python, mas 
programas contêm muitos detalhes - devido a requerimentos 
impostos pela linguagem de programação, ou porque eles devem 
lidar com erros causados por dados corrompidos, ou falhas do 
sistema - e isso pode dificultar a compreensão do algoritmo 
fundamental se estudarmos apenas o código. É por isso que 
preferimos descrever os algoritmos em algo chamado 
pseudocódigo, que mistura português com características que se 
vê em linguagens de programação. 
Aqui está um pseudocódigo para a busca binária, modificado para 
realizar uma busca em um array. As entradas são o array, que 
chamamos de ​array​; o número ​n​ de elementos no ​array​; e o 
alvo​ (target), número buscado primeiramente. A saída é o índice 
do ​alvo​ no ​array​. 
1. Defina ​min = 0​ e ​max = n-1​. 
2. Calcule ​chute​ como sendo a média entre ​max​ e ​min​, 
arrendonde para baixo (então será um número inteiro). 
3. Se ​array[chute]​ for igual ao ​alvo​, então pare. Você o 
encontrou! Retorne ​chute​. 
4. Se o chute for muito baixo, ou seja, ​array[chute] < alvo​, 
então defina ​min = chute + 1​. 
5. Caso contrário, o chute foi muito alto. Defina ​max = chute 
- 1​. 
6. Volte para o passo 2. 
Implementação do pseudocódigo 
Vamos alternar entre português, pseudocódigo e JavaScript nesses 
tutoriais, dependendo da situação. Como programador, você deve 
aprender a entender o pseudocódigo e ser capaz de convertê-lo na 
sua linguagem escolhida - então, embora estejamos usando 
JavaScript aqui, deve ser simples para você implementar 
pseudocódigo em outras linguagens. 
Como poderíamos converter esse pseudocódigo em um programa 
JavaScript? Devemos criar uma função, porque estamos 
escrevendo um código que aceita uma entrada e retorna uma 
saída, e queremos que esse código seja reutilizável para diferentes 
entradas. Os parâmetros da função — vamos chamá-la 
binarySearch​ — serão o array e o valor alvo (target), e o valor 
de retorno da função será o índice da posição onde o valor alvo foi 
encontrado. 
Agora, vamos examinar o corpo principal da função, e decidir como 
implementá-lo. A etapa 6 diz para voltar para a etapa 2. Isso 
parece ser um laço. Ele deve ser um laço for ou um laço while? Se 
você realmente quisesse usar um laço for, poderia fazê-lo, mas os 
índices supostos pela busca binária não estão na ordem sequencial 
que o laço for torna-se conveniente. Primeiro, podemos selecionar 
o índice 12, então o 18, com base em algumas computações. 
Então, um laço while é a melhor opção. 
Há também uma etapa importante faltando nesse pseudocódigo 
que não era importante no jogo de adivinhação, mas é importante 
na busca binária de um array. O que deve acontecer se o número 
que você está procurando ​não​ estiver no array? Vamos começar 
descobrindo qual índice a função ​binarySearch​ deve retornar 
neste caso. O índice deve ser um número que não pode ser válido 
no array. Vamos usar ​-1​, já que este não pode ser um índice 
válido em nenhum array. (Na verdade, qualquer número negativo 
servirá.) 
O número alvo não estará no array se não houver mais possíveis 
chutes. Em nosso exemplo, suponha que estamos procurando pelo 
alvo número 10 no array ​primes​. Se o 10 estivesse lá, ele estaria 
entre os números 7 e 11, que estão nos índices 3 e 4. Se você 
rastrear os índices dos valores para ​min​ e ​max​ assim como a 
função ​binarySearch​ faz, você descobriria que em algum 
momento eles estariam no ponto onde ​min​ é igual a 3 e ​max​ é 
igual a 4. O chute é então o índice 3 (como (3 + 4) / 2 é igual a 3,5, 
e arredondamos para baixo), e ​primes[3]​ é menor que 10, desta 
forma, ​min​ se torna 4. Com ambos, ​min​ e ​max​ valendo 4, o chute 
deve ser o índice 4, e ​primes[4]​ é maior que 10. Agora ​max​ se 
torna 3. O que isso significa, ​min​ ser igual a 4 e ​max​ ser igual a 3? 
Isso significa que os únicos possíveis chutes são no mínimo 4 e no 
máximo 3. Não existe esse número no array! Neste ponto, 
podemos concluir que o alvo 10, não está no array ​primes​, e a 
função ​binarySearch​ retornaria ​-1​. Em geral, uma vez que ​max 
se torna estritamente menor que ​min​, nós sabemos que o número 
alvo não está no array ordenado. A seguir está o pseudocódigo 
modificado para a busca binária que lida com o caso em que o 
número alvo não está no array: 
1. Defina ​min = 0​ e ​max = n-1​. 
2. Se ​max < min​, então pare: o ​alvo​ não está presente no 
array​. Retorne ​-1​. 
3. Calcule o ​chute​ como sendo a média entre ​max​ e ​min​, 
arredondando para baixo (então será um número inteiro). 
4. Se ​array[chute]​ for igual ao ​alvo​, então pare. Você o 
encontrou! Retorne ​chute​. 
5. Se o chute foi muito baixo, ou seja, ​array[chute] < alvo​, 
então defina ​min = guess + 1​. 
6. Caso contrário, o chute foi muito alto. Defina ​max = guess 
- 1​. 
7. Volte para o passo 2. 
Agora que analisamos o pseudocódigo juntos, você vai tentar 
implementar a busca binária por conta própria. Tudo bem dar uma 
olhada no pseudocódigo - de fato, isso é bom, porque assim você 
vai compreender melhor o que significa converter um pseudocódigo 
em um programa. 
Desafio: Busca binária 
Implemente a busca binária 
(Se você não conhecer JavaScript, pode pular os 
desafios de código, ou pode fazer o curso de Introdução 
ao JS e voltar depois). 
Complete a função ​doSearch​ de modo que ela 
implemente uma busca binária, seguida pelo 
pseudocódigo abaixo (esse pseudocódigo foi descrito 
no artigo anterior): 
1. Seja ​min = 0​ e ​max = n-1​. 
2. Se ​max < min​, então pare: O alvo não está 
presente no array. Retorne ​-1​. 
3. Calcule ​guess​ como a média de ​max​ e ​min​, 
arredondada para baixo (de modo que seja um número 
inteiro). 
4. Se ​array[guess]​ for igual ao alvo, então pare. 
Você encontrou! Retorne ​guess​. 
5. Se o palpite for baixo demais, ou seja, 
array[guess]​ ​<​ target, então faça ​min = guess + 
1​. 
6. Caso contrário, o palpite foi alto demais. Faça ​max = 
guess - 1​. 
7. Volte para o passo 2. 
Feita a implementação, retire os comentários da 
instrução ​Program.assertEqual()​ no final para 
verificar se o teste de asserção foi bem-sucedido. 
R: ​var​ ​doSearch​ ​=​ ​function​(​array​, 
targetValue) { 
 ​var​ min ​=​ ​0​; 
 ​var​ max ​=​ ​array​.​length​ ​-​ ​1​; 
 ​var​ guess; 
 ​while​(){ 
 guess ​=​ ; 
 ​if​(​===​){ } 
 ​else​ ​if​(​<​){} 
 ​else​{ } 
 } 
 ​return​ ​-​1​; 
}; 
 
/* Returns either the index of the location in the 
array, 
 or -1 if the array did not contain the targetValue */ 
var doSearch = function(array, targetValue) { 
 var min = 0; 
 var max = array.length - 1; 
var guess; 
 
 
 
 
 return -1; 
}; 
 
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; 
 
var result = doSearch(primes, 73); 
println("Found prime at index " + result); 
 
//Program.assertEqual(doSearch(primes, 73), 20); 
 
 
 
 
 
Como ele chega ao resultado? 
Para visualizar melhor como sua busca binária funciona, 
adicione uma instrução ​println()​que exibe o palpite 
a cada etapa. 
Observação: você deve imprimir o índice do palpite, e 
não o valor do elemento para o qual ele aponta. 
Dica: 
 
var​ ​doSearch​ ​=​ ​function​() { 
 ​while​() { 
 
 println(); 
 
 } 
}; 
 
/* Returns either the index of the location in the 
array, 
 or -1 if the array did not contain the targetValue */ 
var doSearch = function(array, targetValue) { 
 var min = 0; 
 var max = array.length - 1; 
var guess; 
 
 
 
 
 return -1; 
}; 
 
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; 
 
var result = doSearch(primes, 73); 
println("Found prime at index " + result); 
 
//Program.assertEqual(doSearch(primes, 73), 20); 
 
 
Quanto tempo ele leva? 
Para ajudar na visualização do tempo que uma busca 
leva para ser feita, adicione uma instrução ​println() 
que mostra o número total de palpites necessários para 
encontrar o resultado. 
Sua função deve imprimir o número total de palpites 
somente quando ela tiver encontrado o alvo. Sua 
função não deve imprimir o número de palpites em 
todas as repetições do laço. 
Observação: uma busca binária pelo valor alvo ​41​ no 
array ​primes​ requer 1 palpite. 
DicaO que é isto? 
var​ ​doSearch​ ​=​ ​function​() { 
 
 
 ​while​() { 
 
 println(); 
 } 
}; 
 
/* Returns either the index of the location in the 
array, 
 or -1 if the array did not contain the targetValue */ 
var doSearch = function(array, targetValue) { 
 var min = 0; 
 var max = array.length - 1; 
var guess; 
 
 
 
 
 return -1; 
}; 
 
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; 
 
var result = doSearch(primes, 73); 
println("Found prime at index " + result); 
 
//Program.assertEqual(doSearch(primes, 73), 20); 
 
 
Teste! 
Adicione mais duas verificações, abaixo da verificação 
fornecida para 73, usando ​Program.assertEqual() 
para que seu algoritmo de busca encontre a resposta 
correta de forma consistente. Observe como ele chega 
ao resultado em cada vez. 
DicaO que é isto? 
Program.assertEqual(doSearch(primes, ), 
); 
Program.assertEqual(doSearch(primes, ), 
); 
 
/* Returns either the index of the location in the 
array, 
 or -1 if the array did not contain the targetValue */ 
var doSearch = function(array, targetValue) { 
 var min = 0; 
 var max = array.length - 1; 
var guess; 
 
 
 
 
 return -1; 
}; 
 
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]; 
 
var result = doSearch(primes, 73); 
println("Found prime at index " + result); 
 
//Program.assertEqual(doSearch(primes, 73), 20); 
 
 
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​+1 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 lg​n ​\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​: 
n 
n 
n 
\lg 
n 
lg​n 
\lg, 
n 
1 0 
2 1 
4 2 
8 3 
https://pt.khanacademy.org/math/algebra2/exponential-and-logarithmic-functions/introduction-to-logarithms/v/logarithms
Podemos visualizar essa mesma tabela na forma de um gráfico: 
16 4 
32 5 
64 6 
128 7 
256 8 
512 9 
1024 10 
1.048.57
6 
20 
2.097.15
2 
21 
 
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 
\lg n = x 
lg​n​=​x 
\lg, n, equals, x 
, então 
n = 2^x 
n​=2 
x 
n, equals, 2, start superscript, x, end superscript 
. For example, because 
\lg 128 = 7 
lg128=7 
\lg, 128, equals, 7 
, we know that 
2^7 = 128 
2 
7 
=128 
2, start superscript, 7, end superscript, equals, 128 
. 
Quando 
n 
n 
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^{10} 
2 
10 
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^{22} 
2 
22 
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. 
Quiz: Tempo de execução da busca 
binária 
 
Problema 
1. 32 times se classificaram para a Copa do Mundo de 
2014. Se os nomes dos times fossem colocados 
em ordem (em um array), quantos itens no array a 
busca binária teria que examinar para encontrar a 
localização de um time em particular no array, no 
pior caso?​ No máximo, 6 
2. Qual é o lg(32), o logaritmo de 32 na base 2? ​5 
3. Você tem um array contendo os números primos de 
2 a 311 em ordem: ​[2, 3, 5, 7, 11, 13, 
..., 307, 311]​. Há 64 itens no array. Cerca de 
quantos itens do array a busca binária teria que 
examinar antes de concluir que 52 não está no 
array, e portanto não é primo? ​7 
4. Em 2013, havia 193 países membros das Nações 
Unidas. Se os nomes desses países fosse 
ordenado alfabeticamente em um array, cerca de 
quantos nomes a busca binária teriaque examinar 
para encontrar um nome particular no array, no pior 
caso? ​Não mais que 9. 
5. O "Catálogo da Vida" de 2014 contém cerca de 
1580000 nomes de espécies. Se esses nomes 
fossem ordenados em um array, no pior caso, 
quanto tempo demoraria para que a busca binária 
encontrasse o nome de uma espécie em particular 
no array?​ ​No máximo, ele olharia para 22 nomes