Enunciado

Suponha que você esteja procurando um item em uma lista ordenada composta por um milhão de itens. Quantos passos podem ser necessários para encontrar esse item por meio de uma busca sequencial? E por meio de uma busca binária?

Passo 1

Bom, para procurar um item em uma lista ordenada iriamos levar 1 milhão de passos em uma busca sequencial. Agora, caso a busca fosse binária, iriamos levar no máximo 20 passos. Veja porque:

2 19 = 524   288 < 1.000.000

2 20 = 1.048.576 > 1.000.000

Resposta

No máximo 20 passos

Ver Outros Exercícios desse livro

Exercícios de Livros Relacionados

Seja y = 1 1 + x 2 . Encontre os valores de x nos quais y está crescendo e decrescendo mais rapidamente.
53-54. Em cada parte, determine se a afirmação é verdadeira ou falsa. Se falsa, encontre funções para quais a afirmação não é válida.53. a) Se f e g forem crescentes em um intervalo, então f + g també
55. Em cada parte, encontre funções f e g que sejam crescentes em - ∞ ,+ ∞ e com as quais f - g tem a propriedade indicada.c) f - g é crescente em - ∞ ,+ ∞ .
55. Em cada parte, encontre funções f e g que sejam crescentes em - ∞ ,+ ∞ e com as quais f - g tem a propriedade indicada.a) f - g é decrescente em - ∞ ,+ ∞ .
56. Em cada parte, encontre funções f e g que sejam positivas e crescentes em - ∞ ,+ ∞ e com as quais f g tem a propriedade indicada.c) f g é crescente em - ∞ ,+ ∞ .