Considere uma lista ordenada, contendo 20 chaves únicas, na qual seja realizada uma busca binária. Assinale o número máximo de acessos necessários para encontrar uma determinada chave.
- A)4
4 está errada, porque 4 divisões por 2 ainda não garantem localizar com segurança uma chave em uma lista de 20 posições.
- B)5
5 está certa, pois a busca binária precisa no máximo desse número de acessos para cobrir todos os 20 elementos no pior caso.
- C)6
6 está errada, porque superestima o pior caso da busca binária em uma lista com apenas 20 chaves.
- D)10
10 está errada, pois isso se aproxima mais de uma busca linear do que de uma busca binária.
- E)20
20 está errada, porque a busca binária não percorre item por item; ela elimina metade da lista a cada passo.
Gabarito: B
Busca binária funciona como aquele jogo de "quente ou frio": a cada passo, você elimina metade da lista. Como a lista já está ordenada, primeiro você compara com o elemento do meio, depois descarta uma metade e repete o processo na parte que sobrou. Isso faz o número de acessos crescer bem devagar, em ordem logarítmica, e não de forma linear como numa busca simples. Para 20 chaves únicas, o pior caso ocorre quando a chave está lá no fundo da subdivisão e você precisa descer o máximo possível. A conta prática é pensar em quantas divisões por 2 são necessárias para cobrir 20 elementos. Em uma busca binária, isso dá 5 acessos no máximo, porque 2^4 = 16 ainda não basta para abranger 20 posições, e o próximo nível já cobre o intervalo completo. Então o gabarito B está correto: o número máximo de acessos necessários para encontrar a chave, no pior caso, é 5. Em provas, a banca costuma cobrar essa ideia de complexidade O(log n) de forma bem direta, às vezes usando a fórmula aproximada de ceil(log2(n + 1)).