Mostrar código-fonte de Busca exponencial

{{Wikificação|data=dezembro de 2017}}
{{Info/Algoritmo|classe=[[Search algorithm|Algoritmo de Busca]]|caso_medio=[[Big O notation#Orders of common functions|''O''(log ''i'')]]|melhor_caso=[[Big O notation#Orders of common functions|''O''(1)]]|pior_caso=[[Big O notation#Orders of common functions|''O''(log i)]]|complexidade=[[Big O notation#Orders of common functions|''O''(log ''i'')]]|espaco=[[Big O notation#Orders of common functions|''O''(1)]]|data=[[array data structure|Array]]}}

Em [[ciência da computação]], um '''busca''' '''exponencial''' (também chamado '''busca a galope''' ou '''busca Struzik''')<ref name=Baeza-Yates>{{citation|contribuição=Fast intersection algorithms for sorted sequences|primeiro1 =Ricardo|último1 =Baeza-Yates|autorlink1 = Ricardo Baeza-Yates |primeiro2 =Alejandro|último2 =Salinger|título=Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday|volume=6060|series=Lecture Notes in Computer Science|editor-nome1 =Tapio|editor-sobrenome1 =Elomaa|editor-nome2 =Heikki|editor-sobrenome2 =Mannila|editor2-link=Heikki Mannila|editor-nome3 =Pekka|editor-sobrenome3 =Orponen|publicado=Springer|ano=2010|isbn=9783642124754|páginas=45–61|doi=10.1007/978-3-642-12476-1_3}}.</ref> é 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 [[Pesquisa binária|busca binária]] dentro desse intervalo. Isso leva a uma complexidade [[Grande-O|''O'']](log&#x20;''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&#x20;''i''), onde ''i'' é o índice do elemento que está sendo procurado na lista, enquanto que a busca binária tem complexidade de ''O''(log&#x20;''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 [[Exponenciação|expoente]], ''j'', onde o valor de 2{{Exp|j}} é maior do que a chave de pesquisa. Este valor, 2{{Exp|j}}, torna-se o limite superior para a busca binária com a potência de 2 anterior, 2{{Exp|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{{Exp|j - 1}}, e o atual índice de pesquisa, 2{{Exp|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&#x20;''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&#x20;''i'').

A segunda parte do algoritmo também leva ''O''(log&#x20;''i''). Como a segunda fase é simplesmente uma pesquisa binária, leva-se ''O''(log&#x20;''n''), onde ''n'' é o tamanho do intervalo que está sendo pesquisado. O tamanho deste intervalo seria de 2{{Exp|''j''}} - 2{{Exp|''j'' - 1}} onde, como visto acima, ''j'' = log&#x20;''i''. Isto significa que o tamanho do intervalo que está sendo pesquisado é de 2{{Exp|log ''i''}} - 2{{Exp|log ''i'' - 1}} = 2{{Exp|log ''i'' - 1}}. Isso resulta em um tempo de execução de log&#x20;(2{{Exp|log ''i'' - 1}}) = log&#x20;(''i'') - 1 = ''O''(log&#x20;''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&#x20;''i'') + ''O''(log&#x20;''i'') = 2 ''O''(log&#x20;''i'') = ''O''(log&#x20;''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 ''<math>j'</math>'', bem como antes, de modo que <math>2^{j'}</math> seja maior do que a tecla de pesquisa e <math>2^{j'/2}</math> é menor do que a chave de busca. Anteriormente, ''<math>j'</math>'' 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 <math>j'</math> seja duplicado em vez disso (por exemplo, saltando de 22 para 24 em oposição a 23). O primeiro ''<math>j'</math>'' tal que <math>2^{j'}</math> é maior que a chave de busca um limite superior muito mais difícil do que antes. Uma vez que ''<math>j'</math>'' é encontrado, o algoritmo move-se para o segundo estágio e uma busca binária é realizada no intervalo formado por <math>j'/2</math> e <math>j'</math>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{{Exp|''j'' - 1}} and 2{{Exp|''j''}}, como antes. O desempenho desta variação é <math>\lfloor \log i \rfloor + 2 \lfloor \log(\lfloor \log i \rfloor + 1)\rfloor + 1</math> = ''O''(log&nbsp;''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&#x20;''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&#x20;(''d'') + log&#x20;log&#x20;(''d'') + ... + ''S''(log&#x20;{{Exp|*}}''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 Linear]]
* [[Pesquisa binária|Busca binária]]
* Interpolação de pesquisa
* Busca Ternária
* [[Tabela de dispersão|Tabela de Hash]]

== Bibliografia ==
* {{citar periódico
|último1 = Bentley
|primeiro1 = Jon L. |autorlink1 = Jon Bentley (computer scientist)
|último2 = Yao
|primeiro2 = Andrew C. |autorlink2 = Andrew Yao
|título= An almost optimal algorithm for unbounded searching
|ano= 1976
|periódico= [[Information Processing Letters]]
| volume    = 5
|número= 3
|páginas= 82–87
| issn      = 0020-0190
| doi       = 10.1016/0020-0190(76)90071-5
}}
* {{citar web
| url        = https://sites.google.com/site/d7013e11/announcements/exponentialbinarysearch
|acessodata= 2014-03-24
|título= Exponential Binary Search
|primeiro = Håkan
|último = Jonsson
|data= 2011-04-19
}}
* {{citar periódico
|último1 = Andersson
|primeiro1 = Arne
|último2 = Thorup
|primeiro2 = Mikkel |autorlink2 = Mikkel Thorup
|título= Dynamic ordered sets with exponential search trees
|ano= 2007
|periódico= [[Journal of the ACM]]
| volume    = 54
|número= 3
|páginas= 13
| issn      = 0004-5411
| doi       = 10.1145/1236457.1236460
}}

{{Referências}}

[[Categoria:Algoritmos de busca]]