Question

Caso seja empregada uma busca binária em uma lista sequencial ordenada com 2048 valores, qual seria o número máximo de comparações para encontrar um valor que esteja na lista?

Answer 1

Resposta:

12

Explicação:

Em uma busca binária o número maximo de comparações é

$log_{2}(n) + 1$

onde n é o tamanho da lista. Assim temos

$log_{2}(2048) + 1 = 11 + 1 = 12$

Answer 2

Resposta:

A resposta é 11.

Explicação:

Como a busca binária sai continuamente dividindo o conjunto de dados ao meio (em duas partes), então vamos fatorar e organizar o resultado como potência de base 2.

Fatorando 2048 temos 2¹¹