# Busca exponencial

Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik) é um algoritmo, criado por Jon Bentley e Andrew Chi-Chih Yao em 1976, para a busca listas ordenadas ilimitadas. Existem várias maneiras de se implementar este algoritmo, sendo a mais comum determinar um intervalo em que a chave de pesquisa reside e realizar uma busca binária dentro desse intervalo. Isso leva a uma complexidade O(log i), onde i é a posição da chave de pesquisa na lista, se a chave de pesquisa está na lista, ou a posição onde a chave de pesquisa deve estar, caso a chave de pesquisa não está na lista.
A busca exponencial também pode ser usada para pesquisar em listas limitadas. A busca exponencial pode ainda ser mais rápido que os métodos de busca tradicionais, tais como busca binária, quando o elemento a ser procurado é próximo ao início da lista. A razão para isso é que a busca exponencial será executada em O(log i), onde i é o índice do elemento que está sendo procurado na lista, enquanto que a busca binária tem complexidade de O(log n), onde n é o número de elementos na lista.

## Algoritmo

Busca Exponencial permite a pesquisar em uma lista ordenada e sem limites para um determinado valor de entrada (o "valor" a ser buscado na lista). O algoritmo consiste de duas fases. A primeira etapa determina um intervalo em que a chave de pesquisa reside, se existir na lista. Na segunda etapa, uma busca binária é realizada neste intervalo. Na primeira etapa, partindo do princípio que a lista é ordenada de forma ascendente, o algoritmo procura o primeiro expoente, j, onde o valor de 2$^j$ é maior do que a chave de pesquisa. Este valor, 2$^j$, torna-se o limite superior para a busca binária com a potência de 2 anterior, 2$^{j-1}$, sendo este o limite inferior para a busca binária. Em cada passo, o algoritmo compara o valor da chave de pesquisa com o valor da chave no atual índice de pesquisa. Se o elemento no índice atual é menor do que a chave de busca, o algoritmo repete-se, pulando para o próximo índice de pesquisa, duplicando o índice ao calcular a próxima potência de 2. Se o elemento no índice atual é maior do que a chave de busca, o algoritmo agora sabe que o valor a ser pesquisa está localizado no intervalo formado pelo anterior índice de pesquisa, 2$^{j-1}$, e o atual índice de pesquisa, 2$^j$, caso este elemento estiver contido na lista. A busca binária é executada, em seguida. Se a chave não está na lista, a busca binária irá falhar, mas se estiver, a posição da chave na lista é retornada.

## Desempenho

A primeira fase do algoritmo leva a um tempo O(log i), onde i é o índice onde a chave de pesquisa estaria na lista. Isso acontece porque ao determinar o limite superior para a pesquisa binária, o loop while é executado exatamente vezes. Já que a lista é ordenada, depois de dobrar o índice de pesquisa vezes, o algoritmo vai realizar uma busca de índice que é maior do que ou igual a i, tal que. Como tal, a primeira fase do algoritmo leva O(log i).
A segunda parte do algoritmo também leva O(log i). Como a segunda fase é simplesmente uma pesquisa binária, leva-se O(log n), onde n é o tamanho do intervalo que está sendo pesquisado. O tamanho deste intervalo seria de 2$^j$ - 2$^{j-1}$ onde, como visto acima, j = log i. Isto significa que o tamanho do intervalo que está sendo pesquisado é de 2$^{logi}$ - 2$^{logi-1}$ = 2$^{logi-1}$. Isso resulta em um tempo de execução de log (2$^{logi-1}$) = log (i) - 1 = O(log i).
Desta forma, o tempo total de execução do algoritmo, calculado pela soma dos tempos de execução de duas etapas, de O(log i) + O(log i) = 2 O(log i) = O(log i).

## Alternativas

Bentley e Yao sugeriram várias variações para busca exponencial. Essas variações consistem em realizar uma pesquisa binária, em oposição a uma busca unária, ao determinar o limite superior para a busca binária na segunda etapa do algoritmo. Isso divide a primeira etapa do algoritmo em duas partes, tornando o algoritmo um algoritmo de três estágios em geral. O novo primeiro estágio determina um valor $j'$, bem como antes, de modo que $2^{j'}$ seja maior do que a tecla de pesquisa e $2^{j'/2}$ é menor do que a chave de busca. Anteriormente, $j'$ foi determinado de forma unária calculando a próxima potência de 2 (isto é, adicionando 1 a j). Na variação, propõe-se que $j'$ seja duplicado em vez disso (por exemplo, saltando de 22 para 24 em oposição a 23). O primeiro $j'$ tal que $2^{j'}$ é maior que a chave de busca um limite superior muito mais difícil do que antes. Uma vez que $j'$ é encontrado, o algoritmo move-se para o segundo estágio e uma busca binária é realizada no intervalo formado por $j'/2$ e $j'$dando o expoente do limite superior mais preciso j. A partir daqui, a terceira etapa do algoritmo realiza a busca binária no intervalo 2$^{j-1}$ and 2$^j$, como antes. O desempenho desta variação é $\lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1$ = O(log i).
Bentley e Yao generalizam esta variação onde de qualquer número k, de buscas binárias é realizada durante a primeira fase do algoritmo, resultando na variante de busca binárias k-aninhada (k-nested binary search). O tempo de execução não se altera para as variações, sendo executado em O(log i), como com o original exponencial algoritmo de pesquisa.
Além disso, uma estrutura de dados com um versão mais apertada da propriedade das árvores spray pode ser dada quando o resultado acima do pesquisa binária k-aninhada é usada em um array ordenado. Assim, o número de comparações feitas durante uma busca é igual a log (d) + log log (d) + ... + S(log $^*$d), onde d é a diferença de pontuação entre o último elemento que foi acessado e o elemento atual sendo acessada.

## Veja também

* Busca Linear
* Busca binária
* Interpolação de pesquisa
* Busca Ternária
* Tabela de Hash