该搜索算法的名称可能会产生误导，因为它的工作时间为 O(Log n)。该名称来自于它搜索元素的方式。
给定一个已排序的数组和要
搜索的元素 x，找到 x 在数组中的位置。
输入：arr[] = {10, 20, 40, 45, 55}
x = 45
输出：在索引 3 处找到元素
输入：arr[] = {10, 15, 25, 45, 55}
x = 15
输出：元素在索引 1 处找到
我们已经讨论过，线性搜索、二分搜索这个问题。
指数搜索涉及两个步骤：
1、查找元素存在的范围
2、在上面找到的范围内进行二分查找。
如何找到元素可能存在的范围？
这个想法是从子数组大小 1 开始，将其最后一个元素与 x 进行比较，然后尝试大小 2，然后是 4，依此类推，直到子数组的最后一个元素不大于。
一旦我们找到一个索引 i（在重复将 i 加倍之后），我们就知道该元素必须存在于 i/2 和 i 之间（为什么是 i/2？因为我们在之前的迭代中找不到更大的值）下面给出的是上述步骤的实施。
示例：
# Python program to find an element x
# in a sorted array using Exponential Search
# A recursive binary search function returns
# location of x in given array arr[l..r] is
# present, otherwise -1
def binarySearch( arr, l, r, x):
if r >= l:
mid = l + ( r-l ) // 2
# If the element is present at
# the middle itself
if arr[mid] == x:
return mid
# If the element is smaller than mid,
# then it can only be present in the
# left subarray
if arr[mid] > x:
return binarySearch(arr, l,
mid - 1, x)
# Else he element can only be
# present in the right
return binarySearch(arr, mid + 1, r, x)
# We reach here if the element is not present
return -1
# Returns the position of first
# occurrence of x in array
def exponentialSearch(arr, n, x):
# IF x is present at first
# location itself
if arr[0] == x:
return 0
# Find range for binary search
# j by repeated doubling
i = 1
while i < n and arr[i] <= x:
i = i * 2
# Call binary search for the found range
return binarySearch( arr, i // 2,
min(i, n-1), x)
# Driver Code
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponentialSearch(arr, n, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))
# This code is contributed by Harshit Agrawal
输出
元素出现在索引 3 处
时间复杂度： O(Log n)
辅助空间：上述二分查找的实现是递归的，需要 O(Log n) 空间。通过迭代二分搜索，我们只需要 O(1) 空间。
指数搜索的应用：
1、指数二分搜索对于数组大小无限的无界搜索特别有用。请参阅无界二分搜索示例。
2、对于有界数组，以及当要搜索的元素更接近第一个元素时，它比二分搜索效果更好。
