Busca exponencial

Busca exponencial
classe	Algoritmo de Busca
complexidade pior caso	O(log i)
complexidade caso médio	O(log i)
complexidade melhor caso	O(1)
complexidade de espaços pior caso	O(log i)
espaço	O(1)
data	Array
Algoritmos

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^{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).

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

Bibliografia

• 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