O algoritmo descrito a seguir realiza a busca do elemento x no vetor ordenado V, que possui tamanho N. Procedimento busca (V,N,x) A ← 1 Z ← N Enquanto x não for encontrado se Z < A então retorna x não existe em V. m ← A + (Z - A) / 2 se V[m] < x então A ← m + 1 se V[m] > x então Z ← m - 1 se V[m] = x então retorna x encontrado fim Enquanto fim Procedimento Assinale a opção que representa a complexidade do algoritmo utilizando a notação Big O.
- A)O (1)
Errada, porque O(1) seria tempo constante, e aqui o algoritmo faz várias comparações até achar ou descartar o elemento.
- B)O (N)
Errada, porque O(N) corresponde a examinar quase todos os elementos, como na busca linear, o que não acontece neste caso.
- C)O (n * Log2 N)
Errada, porque a busca binária não multiplica N por log N; ela reduz o espaço de busca por metades sucessivas.
- D)O (Log2 N)
Certa, porque o algoritmo é uma busca binária em vetor ordenado, com tempo proporcional ao logaritmo do tamanho do vetor.
- E)O (n^2)
Errada, porque O(n^2) é típico de algoritmos com laços aninhados pesados, o que não existe aqui.
Gabarito: D
Este algoritmo é a busca binária, aquela técnica clássica que divide o problema ao meio a cada passo. Como o vetor já está ordenado, ele compara o valor procurado com o elemento do meio e, com isso, elimina metade das posições de uma vez. Em vez de ir “folheando” o vetor inteiro, como na busca linear, ele vai cortando o espaço de busca de forma muito eficiente. Na prática, em cada repetição o intervalo de busca diminui pela metade. Isso faz com que o número de etapas cresça muito devagar quando o tamanho do vetor aumenta. Por isso, a complexidade de tempo é O(log N), e não O(N) ou algo pior. O fato de usar A, Z e m confirma exatamente essa lógica de busca binária. O gabarito D está correto porque o algoritmo realiza sucessivas divisões por 2 do intervalo considerado. Se você dobra o tamanho do vetor, não dobra o tempo na mesma proporção; aumenta só mais um passo ou poucos passos. Esse comportamento é a marca registrada do logaritmo. Em concursos, vale guardar o trio: busca linear é O(N), busca binária em vetor ordenado é O(log N), e a ordenação prévia do vetor é condição essencial. Sem essa ordem, a estratégia perde o sentido e a eficiência vai embora junto.