Desempenho da busca binária
Quanto tempo a função buscaBinaria consome?
No início da primeira iteração, d - e vale aproximadamente n.
No início da segunda, vale aproximadamente n/2.
No início da terceira, aproximadamente n/4.
No início da (k+1)-ésima, aproximadamente n/2k.
Quando k passar de log n , o valor da expressão n/2k fica menor que 1 e a execução do algoritmo termina.
Logo, o número de iterações é aproximadamente lg (n) no pior caso, sendo lg (n) o piso de log n .
Isso é muito menos que o número de iterações da busca sequencial, pois log transforma multiplicações em somas.
Por exemplo, se uma busca em um vetor de tamanho N exige T iterações, então uma busca em um vetor de tamanho 2N fará apenas 1 + T iterações, uma busca em um vetor de tamanho 8N fará apenas 3 + T iterações, e uma busca em um vetor de tamanho 16N fará apenas 4 + T iterações.
O consumo de tempo da função buscaBinaria é proporcional ao número de iterações e portanto proporcional a log n no pior caso.
http://www.ime.usp.br/~pf/algoritmos/aulas/bubi2.html