GabaritoA — 10
Gabarito: letra A. Em um array ordenado, o algoritmo mais eficiente para buscar um elemento é a busca binária, que no pior caso realiza um número de comparações igual ao teto do logaritmo de base 2 do tamanho do array. Para 1000 elementos, ( \lceil \log_2 1000 \rceil = 10 ) comparações.
A busca binária funciona dividindo repetidamente o intervalo de busca pela metade. A cada comparação, descarta-se metade dos elementos restantes. Assim, o número máximo de comparações é o menor inteiro ( k ) tal que ( 2^k \geq n ). Para ( n = 1000 ), ( 2^9 = 512 < 1000 ) e ( 2^{10} = 1024 \geq 1000 ), logo ( k = 10 ).
Corresponde exatamente a ( \lceil \log_2 1000 \rceil = 10 ). É a resposta correta.
50 comparações não correspondem a nenhum algoritmo de busca eficiente para esse tamanho. Seria o necessário para uma busca linear em um array não ordenado de tamanho 50, mas aqui temos 1000 elementos ordenados.
500 comparações seriam típicas de uma busca linear no pior caso (metade do array), mas o array está ordenado, permitindo busca binária muito mais eficiente.
1000 comparações é o pior caso da busca linear (percorrer todos os elementos). Para um array ordenado, a busca binária reduz drasticamente esse número.
100 comparações seria um número intermediário, mas ainda muito acima do logaritmo. Não corresponde a nenhum algoritmo ótimo para busca em array ordenado.
Sempre que um array estiver ordenado, prefira a busca binária. Calcule o número máximo de comparações como ( \lceil \log_2 n \rceil ). Essa é uma questão clássica de concursos.
Gabarito: letra A.
Link permanente: /questoes/qq400623