Pesquisa binária é um algoritmo empregado na computação para encontrar um item em uma lista ordenada de elementos. Trata-se da complexidade do tempo desse algoritmo no pior caso:

Gabarito

Certo

Comentário do professor

A alternativa O(log n) indica que, no pior caso, o número de comparações cresce de forma logarítmica com o tamanho da lista.

A pesquisa binária só funciona em listas ordenadas. A cada comparação ela descarta metade dos elementos, reduzindo o espaço de busca por 2.

Se a lista tem \(n\) elementos, após \(k\) divisões resta no máximo \(n/2^k\) elementos. A busca termina quando \(n/2^k \le 1\), ou seja, \(k \ge \log_2 n\). Portanto o número de passos necessários no pior caso é \(k = \lceil \log_2 n\rceil\).

Como cada passo realiza trabalho constante além da divisão, a complexidade de tempo é expressa por O(log n), onde a base do logarithmo é irrelevante para a notação assintótica.