第 26 课 - 指数搜索

1. 学习目标

完成本课学习后，你将能够：

理解指数搜索的核心思想及其在特定场景下的优势。
掌握将指数搜索与二分查找相结合的实现方法。
明确指数搜索的适用条件（排序数组）及其时间复杂度。
能够区分指数搜索与其他搜索算法（如二分查找、跳跃搜索）的适用场景。

2. 核心概念

指数搜索（Exponential Search）是一种用于在排序数组中查找元素的搜索算法。它的名字来源于它寻找搜索范围的方式——像指数增长一样，从1开始，通过倍增（1, 2, 4, 8, ...）来快速定位目标元素可能存在的区间。

想象一下，你在一个很长的、有无数页的字典里找一个单词。你不会从第一页开始一页一页地看，也不会每次都直接翻到中间。一个聪明的做法是：

先从第1页开始，然后看第2页、第4页、第8页、第16页……快速向后跳跃，直到找到第一个包含大于或等于目标单词的页面。
一旦找到了这样一个范围（比如，在第8页到第16页之间），你知道目标单词一定在这个区间内（如果存在的话）。
然后，你再对这个较小的区间（第8页到第16页）使用更精细的方法（如二分查找）来快速定位目标单词。

指数搜索的核心正是这个“先粗后精”的两阶段过程：

阶段一（指数增长）： 通过 i = 1, 2, 4, 8, ... 快速倍增，找到上界 i 使得 arr[i] >= target。
阶段二（二分查找）： 在找到的范围 [i/2, min(i, n-1)] 内执行标准的二分查找。

为什么使用指数搜索？

优势： 它特别适用于处理长度未知或理论上非常大的数据集（如数据库、外部存储）。它只需要知道元素是排序的，而无需预先知道数组大小。找到范围后，二分查找保证了查找的效率。
复杂度： 时间复杂度为 O(log i)，其中 i 是目标元素的位置。在最坏情况下（目标在数组末尾），它退化到 O(log n)，与二分查找相同。但在目标靠近数组起始位置时，它可能比标准二分查找更快，因为它能更快地缩小搜索的起始范围。

3. 代码示例

下面是一个完整的Python实现。我们将分两步：先实现指数增长找到范围，再在范围内进行二分查找。

def binary_search(arr, left, right, target):
    """
    标准二分查找，在数组的指定区间 [left, right] 内查找目标值。
    """
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到目标

def exponential_search(arr, target):
    """
    指数搜索算法。
    :param arr: 排序后的数组
    :param target: 要查找的目标值
    :return: 目标值在数组中的索引，未找到则返回 -1
    """
    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 倍增：1, 2, 4, 8, ...
    
    # 此时，i/2 是可能包含目标的下界，i 是可能包含目标的上界（可能超出数组）
    # 阶段二：在区间 [i//2, min(i, n-1)] 内进行二分查找
    left_bound = i // 2
    right_bound = min(i, n - 1)
    return binary_search(arr, left_bound, right_bound, target)

# 测试代码
if __name__ == "__main__":
    # 测试用例1：目标存在于数组中
    sorted_array = [2, 5, 8, 12, 16, 23, 38, 45, 67, 91]
    target_value = 23
    result = exponential_search(sorted_array, target_value)
    print(f"在数组 {sorted_array} 中查找 {target_value}，索引为: {result}")  # 预期输出: 5

    # 测试用例2：目标不存在
    target_value_2 = 15
    result_2 = exponential_search(sorted_array, target_value_2)
    print(f"在数组 {sorted_array} 中查找 {target_value_2}，索引为: {result_2}")  # 预期输出: -1

    # 测试用例3：目标是第一个元素
    target_value_3 = 2
    result_3 = exponential_search(sorted_array, target_value_3)
    print(f"在数组 {sorted_array} 中查找 {target_value_3}，索引为: {result_3}")  # 预期输出: 0

    # 测试用例4：目标是最后一个元素
    target_value_4 = 91
    result_4 = exponential_search(sorted_array, target_value_4)
    print(f"在数组 {sorted_array} 中查找 {target_value_4}，索引为: {result_4}")  # 预期输出: 9

4. 实践练习

练习1：基础实现

要求： 不参考示例代码，自己实现 exponential_search 函数。请确保函数能正确处理空数组、目标在首位和目标不在数组中的情况。
测试用例： arr = [1, 3, 5, 7, 9], target = 5。预期输出索引为 2。

练习2：查找边界

要求： 修改 exponential_search 函数，使其不仅返回找到的索引，还能返回在指数增长阶段找到的 上界索引 i。如果未找到，返回 (-1, i)。
提示： 函数返回值可以是一个元组 (found_index, upper_bound_index)。
测试用例： arr = [2, 5, 8, 12, 16, 23, 38, 45], target = 38。预期输出类似 (6, 8) (索引6，上界索引8)。

练习3：应用场景思考

要求： 假设你有一个函数 get_element(index)，它可以获取一个极大且排序的虚拟数组中下标为 index 的元素，但你无法获得整个数组，也无法知道它的总长度 n。如何修改上面的 exponential_search 代码来实现对这个虚拟数组的搜索？
提示： 你需要在指数增长阶段通过调用 get_element(i) 来判断边界，而不是直接访问 arr[i]。思考循环终止条件如何变化。

5. 常见错误

数组未排序： 指数搜索的前提是输入数组必须是升序排列的。如果数组无序，算法将失效。
下标越界： 在指数增长阶段，必须始终检查 i < n，否则 arr[i] 会导致索引错误。
二分查找区间错误： 阶段二的区间必须正确设置为 [i//2, min(i, n-1)]。i//2 确保下界不会错过可能的结果，min(i, n-1) 确保上界不越界。
忽略特殊位置： 没有在函数开始时检查 arr[0] == target，虽然不影响正确性，但可能影响效率。
与跳跃搜索混淆： 指数搜索的目标是快速缩小到一个可能包含目标的小区间，然后在这个区间内进行二分查找。而跳跃搜索是固定步长跳跃，找到第一个大于等于目标的块后，在前一块内进行线性搜索。两者的应用场景和效率特性不同。

6. 小结

指数搜索 是一个两阶段算法：第一阶段通过指数增长（倍增）快速定位一个可能包含目标元素的有界区间，第二阶段在这个区间内执行二分查找。
它的时间复杂度为 O(log i)，其中 i 是目标元素的位置，因此对于靠近数组开头的元素查找非常高效。
它的主要优势在于处理长度未知或动态增长的排序数据集，因为它不需要预先知道数组的大小。
核心实现要点：注意循环条件（i < n and arr[i] <= target）以防止越界，并确保二分查找的区间正确设定为 [i//2, min(i, n-1)]。
它是二分查找的一个智能变体，结合了“粗略定位”和“精确查找”的思想，是工具箱中一个有用的算法。

练习编辑器

rust