A complexidade do algoritmo de busca binária numa lista ordenada, com N elementos, é
- A)O (log N)
Correta, porque a busca binária divide a lista ao meio a cada passo, resultando em complexidade O(log N).
- B)O (N log N)
Errada, pois O(N log N) é complexidade típica de algoritmos de ordenação eficientes, não da busca binária.
- C)O (N)
Errada, porque O(N) seria percorrer a lista elemento por elemento, como na busca linear.
- D)O (N/2)
Errada, já que N/2 ainda cresce linearmente com N e não representa a redução por metades sucessivas da busca binária.
- E)O (N2 )
Errada, pois O(N2) é complexidade quadrática, muito maior do que a da busca binária.
Gabarito: A
A busca binária funciona como quem procura um nome em uma agenda já organizada: em vez de olhar item por item, você abre no meio, compara e descarta metade da lista de uma vez. Depois, repete a lógica na metade que sobrou. Esse “corte ao meio” sucessivo faz a quantidade de passos crescer muito devagar, mesmo quando N aumenta bastante. Por isso, a complexidade da busca binária é O(log N). O logaritmo aparece justamente porque, a cada comparação, o problema fica pela metade. Se a lista tivesse 8 elementos, você precisaria de poucas verificações; com 16, aumenta só mais um passo relevante, e assim por diante. É importante lembrar que essa eficiência só vale se a lista estiver ordenada. Sem ordenação, não há como decidir qual metade descartar, e aí a estratégia deixa de funcionar. Então o gabarito A está correto porque a busca binária não percorre todos os elementos nem depende de operações mais pesadas como ordenação completa. Ela só vai afinando a busca até encontrar o valor ou concluir que ele não existe.