Pesquisa exponencial

A pesquisa binária precisa de saber onde a lista acaba antes de olhar para o meio. A pesquisa exponencial não: avança a galope em passos cada vez maiores até ultrapassar o valor procurado, e depois aplica a pesquisa binária ao último passo. Isso torna-a ideal para listas de comprimento desconhecido, e rápida para valores perto do início.

Uma fila ordenada de barras com saltos que duplicam de comprimento sobre as posições 1, 2, 4 e 8, e o intervalo entre os dois últimos saltos sombreado
Uma fila ordenada de barras com saltos que duplicam de comprimento sobre as posições 1, 2, 4 e 8, e o intervalo entre os dois últimos saltos sombreado

A ideia

Verifique o valor na posição 1, depois na 2, 4, 8, 16 e assim por diante, cada posição o dobro da anterior. Enquanto o valor nessa posição for menor do que o valor procurado, este tem de estar mais à frente. Na primeira vez que um valor não é menor, o valor procurado fica encurralado: está depois da posição verificada antes e não mais à frente do que esta. Esse intervalo está ordenado, por isso uma pesquisa binária encontra o valor procurado, ou mostra que não está lá.

Um exemplo

Procure 23 em 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. A posição 1 tem 2, a posição 2 tem 5, a posição 4 tem 12, todos menores. A posição 8 tem 56, que é maior, por isso 23 só pode estar nas posições 5 a 7. A pesquisa binária verifica a do meio, a posição 6, e encontra 23: 5 comparações, onde a pesquisa binária simples precisa de 3. Procurar 12 na mesma lista para na posição 4 após 3 comparações, menos uma do que a pesquisa binária, e 2 é encontrado na posição 1 com uma única comparação.

Quantas comparações

Para um valor na posição i, a duplicação para após cerca de log₂ i passos e deixa um intervalo de menos de i posições, que a pesquisa binária percorre em cerca de mais log₂ i. Assim, a pesquisa custa cerca de 2 log₂ i comparações, seja qual for o comprimento da lista. Quando o valor procurado está perto do início, isso bate a pesquisa binária, que paga sempre cerca de log₂ n. Quando está perto do fim, a pesquisa exponencial paga até cerca do dobro. Para 40 valores, a aplicação faz em média cerca de 3 comparações nas cinco primeiras posições e cerca de 9 nas cinco últimas, contra cerca de 4,6 da pesquisa binária.

Comprimento desconhecido e galope

Jon Bentley e Andrew Yao descreveram esta estratégia de duplicação em 1976 para a pesquisa ilimitada: encontrar um valor numa sequência ordenada sem fim conhecido, como uma lista infinita ou um fluxo que só se pode sondar. A mesma ideia acelera a fusão. Quando uma de duas sequências ordenadas continua a ganhar, o Timsort passa ao modo galope: olha 1, 2, 4, 8 posições à frente na outra sequência para encontrar onde fica o valor seguinte, em vez de avançar uma posição de cada vez.

Explore

Abra a aplicação, escolha um valor em Procurar e prima Avançar. Cada verificação das posições 1, 2, 4, 8 e assim por diante é destacada; assim que um valor não é menor, o intervalo entre as duas últimas posições fica sombreado e a pesquisa binária assume. Procure um valor pequeno e depois um grande, e compare a contagem com o contador da pesquisa binária.

Perguntas frequentes

Qual é a complexidade temporal da pesquisa exponencial?

O(log i) para um valor na posição i, portanto no máximo O(log n) para uma lista de n valores. Precisa de O(1) de memória adicional e de uma lista ordenada.

Qual é a diferença entre a pesquisa exponencial e a pesquisa binária?

A pesquisa binária começa com a lista inteira e precisa do seu comprimento. A pesquisa exponencial começa por encontrar, duplicando, um intervalo que contém o valor procurado, e depois aplica a pesquisa binária só a esse intervalo. É mais rápida quando o valor procurado está perto do início e funciona sem saber o comprimento.

Porquê duplicar o passo e não somar um valor fixo?

Somar um passo fixo é a pesquisa por saltos, que para atravessar a lista precisa de cerca de n a dividir pelo passo verificações. Duplicar chega à posição i em cerca de log₂ i verificações, e o intervalo que fica nunca é mais do dobro do necessário, por isso a pesquisa binária a seguir continua curta.

Onde se usa a pesquisa exponencial?

Na pesquisa em dados ordenados ilimitados ou muito longos, na fusão de sequências ordenadas (o galope do Timsort) e para encontrar a primeira posição em que uma condição se torna verdadeira quando não se conhece um limite superior.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimente a pesquisa exponencial