Busca exponencial 📖 Wikipedia

Em ciência da computação, um busca exponencial (também chamado busca a galope ou busca Struzik)^[1] é 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.

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.

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^{log i} - 2^{log i - 1} = 2^{log i - 1}. Isso resulta em um tempo de execução de log (2^{log i - 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).

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 ${\displaystyle j'}$, bem como antes, de modo que ${\displaystyle 2^{j'}}$ seja maior do que a tecla de pesquisa e ${\displaystyle 2^{j'/2}}$ é menor do que a chave de busca. Anteriormente, ${\displaystyle 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 ${\displaystyle j'}$ seja duplicado em vez disso (por exemplo, saltando de 22 para 24 em oposição a 23). O primeiro ${\displaystyle j'}$ tal que ${\displaystyle 2^{j'}}$ é maior que a chave de busca um limite superior muito mais difícil do que antes. Uma vez que ${\displaystyle j'}$ é encontrado, o algoritmo move-se para o segundo estágio e uma busca binária é realizada no intervalo formado por ${\displaystyle j'/2}$ e ${\displaystyle 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 é ${\displaystyle \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.

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

• Bentley, Jon L.; Yao, Andrew C. (1976). «An almost optimal algorithm for unbounded searching». Information Processing Letters. 5 (3): 82–87. ISSN 0020-0190. doi:10.1016/0020-0190(76)90071-5 
• Jonsson, Håkan (19 de abril de 2011). «Exponential Binary Search». Consultado em 24 de março de 2014 
• Andersson, Arne; Thorup, Mikkel (2007). «Dynamic ordered sets with exponential search trees». Journal of the ACM. 54 (3). 13 páginas. ISSN 0004-5411. doi:10.1145/1236457.1236460 

Referências