LeetCode 指数搜索题解题目描述实现指数搜索算法在一个有序整数数组中查找目标值。示例输入[11, 12, 22, 25, 34, 64, 90]目标值22输出2目标值在数组中的索引解题思路方法指数搜索思路指数搜索的核心思想是通过指数增长的方式快速定位目标值所在的区间然后在该区间内进行二分搜索。具体步骤从数组的第一个元素开始以指数增长的方式查找目标值。如果当前位置的元素小于目标值则将搜索范围扩大一倍。如果当前位置的元素大于目标值则在最后一次搜索范围的区间内进行二分搜索。如果找到目标值返回其索引否则返回 -1。复杂度分析时间复杂度O(log n)其中 n 是数组的长度。指数搜索的时间复杂度与二分搜索相同。空间复杂度O(1)只需要常数级的额外空间。代码实现方法指数搜索# 指数搜索 def exponential_search(arr, target): n len(arr) if n 0: return -1 # 如果目标值在第一个位置 if arr[0] target: return 0 # 以指数增长的方式查找目标值所在的区间 i 1 while i n and arr[i] target: i * 2 # 在区间 [i/2, min(i, n)) 内进行二分搜索 return binary_search(arr, target, i // 2, min(i, n) - 1) # 二分搜索辅助函数 def binary_search(arr, target, left, right): while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 else: right mid - 1 return -1 # 测试 def test_exponential_search(): arr [11, 12, 22, 25, 34, 64, 90] print(exponential_search(arr, 22)) # 输出2 print(exponential_search(arr, 100)) # 输出-1 print(exponential_search(arr, 11)) # 输出0 if __name__ __main__: test_exponential_search()测试用例测试用例 1基本情况输入[11, 12, 22, 25, 34, 64, 90]目标值22输出2测试用例 2目标值不存在输入[11, 12, 22, 25, 34, 64, 90]目标值100输出-1测试用例 3目标值在第一个位置输入[11, 12, 22, 25, 34, 64, 90]目标值11输出0总结指数搜索是一种高效的搜索算法它通过指数增长的方式快速定位目标值所在的区间然后在该区间内进行二分搜索。指数搜索适用于有序数组其时间复杂度为 O(log n)与二分搜索相同。指数搜索的核心思想是通过指数增长的方式快速定位目标值所在的区间然后在该区间内进行二分搜索。掌握指数搜索的原理和实现对于理解搜索算法的基本思想非常重要。