GabaritoA — O (log N)
Gabarito: letra A. A busca binária divide repetidamente o espaço de busca pela metade, resultando em complexidade O(log N) no pior caso. Isso porque, a cada iteração, descarta-se metade dos elementos restantes, e o número de iterações necessárias para encontrar um elemento (ou concluir que não existe) é aproximadamente log₂(N). Esse é um resultado clássico da análise de algoritmos, estudado em qualquer curso introdutório de estruturas de dados.
O algoritmo funciona apenas em listas ordenadas. Seu princípio é comparar o elemento buscado com o elemento do meio da lista:
Se igual, retorna a posição.
Se menor, busca-se na metade esquerda.
Se maior, busca-se na metade direita.
Esse processo se repete até que a lista seja reduzida a zero elementos ou o elemento seja encontrado. O número de comparações no pior caso é o número de vezes que podemos dividir N por 2 até chegar a 1, ou seja, ⌈log₂(N)⌉.
A alternativa afirma que a complexidade é O(log N). Isso está correto, pois a cada passo o tamanho do problema é reduzido à metade, levando a uma quantidade de passos proporcional ao logaritmo de N na base 2. A notação O-grande abstrai a base do logaritmo, já que logaritmos em diferentes bases diferem apenas por uma constante multiplicativa.
O(N log N) é a complexidade típica de algoritmos de ordenação eficientes, como Merge Sort e Heap Sort. A busca binária não ordena os dados; ela apenas pesquisa em uma lista já ordenada. Portanto, essa alternativa confunde busca com ordenação.
O(N) é a complexidade da busca linear (ou sequencial), que percorre todos os elementos um a um. A busca binária é muito mais rápida para listas grandes, justamente por usar a estratégia de divisão e conquista, resultando em complexidade logarítmica.
O(N/2) ainda é da ordem linear (O(N)), pois o fator constante 1/2 é irrelevante na análise assintótica. A busca binária realiza muito menos operações: para N=1.000.000, a busca linear faria até 1.000.000 comparações, enquanto a binária faria apenas cerca de 20 (log₂ 10⁶ ≈ 20).
O(N²) é uma complexidade quadrática, típica de algoritmos como Bubble Sort, Selection Sort ou certos algoritmos ingênuos. A busca binária é exponencialmente mais eficiente; mesmo para N imenso, o número de operações cresce muito lentamente.
Para memorizar as complexidades básicas, associe a busca binária a divisão sucessiva por 2. Se a cada passo você divide o problema pela metade, o número de passos é logarítmico. Compare com a busca linear, que é O(N), e com a ordenação eficiente, que é O(N log N). Na prova, se precisar calcular mentalmente, lembre-se de que log₂(1.000) ≈ 10, log₂(1.000.000) ≈ 20, log₂(1.000.000.000) ≈ 30. Isso mostra como O(log N) é extremamente eficiente.
Gabarito: letra A.
Link permanente: /questoes/fg049449