指数搜索是一种在有序数组中查找特定元素的搜索算法。它结合了二分搜索和线性搜索的优点，特别适用于未知大小的有序数组。

算法原理

  1. 从数组的起始位置开始，将索引初始化为 i = 0。
  2. 计算指数 exp = 1，这是数组的长度。
  3. 当 arr[exp - 1] 小于或等于待查找的值时，增加 exp 的值，直到 arr[exp - 1] 大于待查找的值。
  4. 如果 arr[exp - 1] 等于待查找的值，则找到了元素。
  5. 如果 exp 超出了数组的长度，则使用线性搜索在数组中查找元素。

代码示例

以下是一个使用 Python 实现指数搜索的例子：

def exponential_search(arr, x):
    if arr[0] == x:
        return 0

    i = 1
    while i < len(arr) and arr[i] <= x:
        i *= 2

    # 使用二分搜索在子数组中查找 x
    return binary_search(arr, x, i // 2, min(i, len(arr) - 1))

def binary_search(arr, x, low, high):
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

# 示例数组
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = 5

# 查找 x 在 arr 中的位置
result = exponential_search(arr, x)
print("Element found at index:", result)

扩展阅读

想了解更多关于算法的知识？可以阅读我们网站的算法教程。

algorithms