LeetCode 指数搜索题解

LeetCode 指数搜索题解

题目描述

实现指数搜索算法，在一个有序整数数组中查找目标值。

示例：

输入：[11, 12, 22, 25, 34, 64, 90]，目标值：22
输出：2（目标值在数组中的索引）

解题思路

方法：指数搜索

思路：

• 指数搜索的核心思想是通过指数增长的方式快速定位目标值所在的区间，然后在该区间内进行二分搜索。
• 具体步骤：
  1. 从数组的第一个元素开始，以指数增长的方式查找目标值。
  2. 如果当前位置的元素小于目标值，则将搜索范围扩大一倍。
  3. 如果当前位置的元素大于目标值，则在最后一次搜索范围的区间内进行二分搜索。
  4. 如果找到目标值，返回其索引；否则，返回 -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)，与二分搜索相同。

指数搜索的核心思想是：通过指数增长的方式快速定位目标值所在的区间，然后在该区间内进行二分搜索。

掌握指数搜索的原理和实现，对于理解搜索算法的基本思想非常重要。