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