Questão de Tecnologia da Informação · CESGRANRIO Transpetro PSP-RH-2018.1 (nº 68)

A busca binária funciona dividindo o espaço de busca pela metade a cada iteração. O número máximo de iterações para encontrar um elemento (ou concluir que ele não existe) em um vetor de tamanho $n$ é dado por $\lceil \log_2(n+1) \rceil$ ou, na prática, $\lfloor \log_2(n) \rfloor + 1$. Para $n = 750$, temos $\log_2(750) \approx 9,55$, então o teto é 10 iterações. A "pegadinha" clássica é confundir $\log_2(750) \approx 9,55$ com 9 (arredondando para baixo), mas como o algoritmo precisa de uma iteração extra para verificar o último elemento ou a condição de término, o máximo é 10.

• (A) Incorreta: 8 seria o máximo para um vetor de até 255 elementos ($2^8 - 1$), muito menor que 750.
• (B) Incorreta: 9 é a armadilha da banca: $\log_2(750) \approx 9,55$, mas o algoritmo não faz iterações fracionárias — ele precisa de 10 iterações completas para cobrir todos os casos, pois $2^9 = 512 < 750 \le 1024 = 2^{10}$.
• (C) Correta: Com 750 elementos, o pior caso exige $\lceil \log_2(750+1) \rceil = \lceil \log_2(751) \rceil = 10$ iterações, pois $2^9 = 512$ não é suficiente para distinguir todos os 750 índices possíveis, e $2^{10} = 1024$ cobre.
• (D) Incorreta: 11 seria necessário apenas para vetores com mais de 1024 elementos (até 2047), o que não é o caso.
• (E) Incorreta: 12 seria para vetores entre 2048 e 4095 elementos, muito além dos 750 do enunciado.