É feita uma pesquisa binária em uma array com 600 elementos. No pior caso, qual dos seguintes números representa a melhor aproximação do número de iterações do algoritmo?

Alternativa B - 10

A Pesquisa Binária (ou Binary Search) é um algoritmo eficiente que funciona dividindo repetidamente o intervalo de busca pela metade. Para entender o número de iterações no pior caso, devemos analisar sua complexidade de tempo, que é logarítmica, representada por $O(\log_2 n)$.

Análise do Problema

Para encontrar o número máximo de passos necessários, precisamos determinar quantas vezes podemos dividir o tamanho do array (n=600) pela metade antes de chegar a 1 elemento restante. Matematicamente, isso equivale a resolver a equação:

Vamos observar as potências de 2 próximas a 600:

Como $600$ está entre $512$ ($2^9$) e $1024$ ($2^{10}$), o número de iterações necessárias será aproximadamente 10.

Por que as outras alternativas estão incorretas?

• Alternativa A (6): Representaria um array de apenas $2^6 = 64$ elementos.
• Alternativa C (100): Seria um crescimento muito rápido para um logaritmo, mas ainda menor que a entrada real.
• Alternativas D e E (300 e 600): Representariam uma busca linear (onde se verifica cada elemento um por um), o que é muito ineficiente para grandes volumes de dados comparado à busca binária.

Portanto, a melhor aproximação para o número de iterações no pior caso é 10.