1. 简介
Exponential Search（指数搜索）是一种适用于无界有序集合的搜索算法，特别适合在非常大的数组或无限序列中查找目标值。
与传统的 Binary Search（二分查找）不同，Exponential Search 不要求整个数组都在内存中，它只需要能够访问任意位置的元素即可。这使得它在处理超大数组或函数定义域为无限整数的情况时表现出色。
2. 无界搜索场景
通常，Binary Search 要求我们有一个完整的、有限的、有序数组。但在以下场景中，Binary Search 可能不再适用：
- 数组太大，无法全部加载进内存；
- 搜索对象不是数组，而是一个函数定义域为无限整数的有序序列（如
f(n)）。
这种情况下，我们面对的是无界搜索问题（Unbounded Search Problem）。此时，Exponential Search 就是一个更合适的选择。
✅ 适用前提：
- 能够通过整数索引访问元素；
- 数据是有序的（非降序）。
3. Exponential Search 原理
Exponential Search 分为两个阶段：
3.1 第一阶段：确定搜索区间
我们从索引 1 开始，逐步将搜索范围翻倍，直到找到一个区间 [2^j, 2^(j+1))，使得目标值 z 落在这个范围内。
例如：
- 检查
x[1] <= z < x[2] - 不满足则检查
x[2] <= z < x[4] - 再检查
x[4] <= z < x[8] - …以此类推，直到找到合适的区间
这个阶段的时间复杂度为 O(log m)，其中 m 是目标值在数组中的位置。
3.2 第二阶段：在区间内执行二分查找
一旦确定了目标值所在的范围 [2^j, 2^(j+1))，我们就在这个子数组中执行 Binary Search，进一步定位目标值的具体位置。
这部分的时间复杂度也为 O(log m)，因此整个算法的时间复杂度为：
✅ O(log m)
⚠️ 注意：如果目标值不在数组中，算法会返回
false或-1。
3.3 示例图示
下图展示了 Exponential Search 如何逐步缩小搜索范围：
3.4 示例说明
假设我们要在一个非常大的数组中查找第 17 个位置的元素：
- 首先检查
x[1] <= z < x[2] - 不满足 → 检查
x[2] <= z < x[4] - 继续检查
x[4] <= z < x[8] - 直到
x[16] <= z < x[32]，发现目标值在这个区间 - 最后在
[16, 31]范围内执行 Binary Search 找到目标值
整个过程仅需 5 步，效率远高于从头开始扫描。
4. 伪代码实现
algorithm ExponentialSearch(x, z):
// x: 有序数组或无限有序序列
// z: 要查找的目标值
// 返回值: z 在 x 中的索引，若不存在则返回 false
j <- 0
n <- x.length // 若为无限序列，设为足够大的值或动态判断
while (j < n) and not (x[2^j] <= z < x[2^(j+1)]):
j <- j + 1
// 在 [2^j, 2^(j+1)-1] 区间内执行 Binary Search
k <- BinarySearch(x, z, 2^j, 2^(j+1) - 1)
if k == false:
return false
else:
return 2^j + k - 1 // 调整索引偏移
⚠️ 注意：在实际编程中，要小心处理
2^j的溢出问题，尤其是在 Java 中使用int类型时。
5. 时间复杂度分析
| 阶段 | 操作 | 时间复杂度 |
|---|---|---|
| 第一阶段 | 找到目标区间 | O(log m) |
| 第二阶段 | 在区间内执行 Binary Search | O(log m) |
| 总计 | O(log m) |
✅ 优势：
- 当目标值靠近数组起始位置时，Exponential Search 比传统 Binary Search 更快；
- 特别适合处理非常大的数组或无限序列。
6. 小结
Exponential Search 是一种高效、实用的搜索算法，尤其适用于以下场景：
- 数组太大，无法一次性加载进内存；
- 搜索对象是函数定义域为无限整数的有序序列；
- 目标值靠近数组起始位置。
虽然它的实现比 Binary Search 稍复杂，但其在特定场景下的性能优势非常明显，是高级程序员应掌握的搜索技巧之一。
✅ 使用建议：
- 确保数组或序列是有序的；
- 注意处理索引越界和溢出问题；
- 适用于大数据量、内存受限或无界搜索场景。
⚠️ 踩坑提醒：
- 不要盲目在小数组中使用 Exponential Search，Binary Search 更简单高效；
- 实现时注意
2^j的计算方式，避免重复计算或溢出。