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