O tempo de execução de um algoritmo é importante na avaliação de problemas e soluções computacionais. Esse fator está estreitamente ligado à complexidade do algoritmo e ao número de elementos de dados que serão processados no pior caso. Numa busca num array com N elementos ordenados, assinale a complexidade algorítmica para a localização de um determinado elemento por meio da busca binária.
- A)2 . N
Errada, porque 2.N representa crescimento linear com um fator constante, e a busca binária não examina todos os elementos.
- B)log N
Certa, pois a busca binária reduz pela metade o espaço de busca a cada passo, gerando complexidade log N.
- C)N
Errada, porque N é a complexidade da busca sequencial, não da busca binária.
- D)N . log N
Errada, porque N.log N aparece em algoritmos como alguns métodos de ordenação, mas não na busca binária.
- E)N ²
Errada, porque N² indica crescimento quadrático, muito maior do que o comportamento da busca binária.
Gabarito: B
Quando a busca é binária, você não vai testando elemento por elemento. A ideia é mais esperta: comparar o valor procurado com o elemento do meio do array, eliminar metade da lista e repetir o processo. Isso faz o trabalho crescer devagar, mesmo quando o número de dados aumenta bastante. Por isso, em um array ordenado com N elementos, a busca binária tem complexidade O(log N). A cada passo, o espaço de busca cai pela metade: N, N/2, N/4, N/8... até sobrar um único elemento ou ficar claro que o item não está lá. Esse comportamento é o que derruba o tempo de execução. Na prática, isso é muito melhor do que uma busca linear, que percorre um a um e vira O(N). Aqui está o pulo do gato: a ordenação do array é o que permite cortar o problema ao meio a cada comparação. Sem ordenação, a busca binária não funciona direito. Então o gabarito B está correto porque a busca binária em um array ordenado tem crescimento logarítmico. Em linguagem de prova: no pior caso, a quantidade de comparações é proporcional a log N.