Enunciado

Suponha que você esteja procurando um item em uma lista ordenada composta por 450 mil itens ( extensão de todo o WebstersThird New International Dictionary). 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 450.000 de passos em uma busca sequencial. Agora, caso a busca fosse binária, iriamos levar no máximo 19 passos. Veja porque:

2 18 = 262.144 < 450.000

2 19 = 524   288 > 450.000

Resposta

No máximo 19 passos

Ver Outros Exercícios desse livro

Exercícios de Livros Relacionados

Determine os pontos críticos das seguintes funções, se existirem.(g) y = x 4 + 4 x 3
Esboce o gráfico de uma função que satisfaça todas as condições dadas. f ' 0 = f ' 2 = f ' 4 = 0 , f ' x0 se x0 ou 2x4 , f ' x0 se 0x2 ou x4 , f ' ' x0 se 1x3 , f ' ' x0 se x1 ou x3
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.b) f g é constante em - ∞ ,+ ∞ .
Use a parte a) do Exercício 59 para mostrar que f x = x + s e nx é crescente no intervalo - ∞ ,+ ∞ .
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. b) Se f e g forem crescentes em um intervalo, então f . g també