Dificuldade ★☆☆
2 minutos de Leitura 🕒
A Busca Exponencial (Exponential Search) é um algoritmo de busca criado por Jon Bentley e Andrew Chi-Chih Yao em 1976 que é capaz de procurar um elemento em um arranjo ordenado ilimitado (um arranjo que possui o limite superior desconhecido). O algoritmo consiste em uma combinação dos algoritmos de Busca Sequencial e Busca Binária, usando o primeiro algoritmo para restringir o espaço de busca e o segundo algoritmo para efetivamente procurar o elemento desejado.
O(log₂ i), onde i é a posição do elemento buscado no arranjo de entrada.i como 1 e n como o comprimento do arranjo.i for menor que n e o elemento no índice i for menor que o elemento procurado, dobre o valor de i.i/2 até min(n, i).O melhor caso do algoritmo de Busca Exponencial ocorre quando o elemento procurado é o primeiro elemento considerado. Nesse cenário, o algoritmo tem um custo constante de comparações:
O(1) comparaçõesO pior caso do algoritmo de Busca Exponencial ocorre quando o elemento procurado não está presente no arranjo de entrada. Nesse cenário, o algoritmo tem um custo logarítmico de comparações, em função do número elementos n no arranjo:
O(log₂ n) comparaçõesVeja o código completo no GitHub.