Explique por que a complexidade da busca binária é expressa através do logaritmo do tempo de execução.

A pesquisa binária funciona num array ordenado, dividindo a área de pesquisa ao meio em cada passo. Em cada passo, ela exclui metade dos elementos restantes, pelo que a quantidade de elementos que precisam ser verificados diminui numa progressão geométrica.

Se inicialmente temos n elementos, após o primeiro passo ficam n/2, depois n/4, n/8 e assim por diante, até sobrar um único elemento. A quantidade dessas divisões é o número de passos do algoritmo, e é igual ao número k, para o qual ( n / 2^k = 1 ).

Resolvendo a equação, obtemos:

[ 2^k = n \implies k = \log_2 n ]

Assim, o tempo de execução da busca binária é proporcional ao logaritmo do tamanho dos dados de entrada, ou seja, (O(\log n)). Isto é muito mais eficiente do que a busca linear com (O(n)).